# Label groups of vertices in a graph in an efficient manner without BFS/DFS

I have a graph with a set of vertices $$\mathcal{V}$$ and a set of edges $$\mathcal{E}$$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $$w(e), e \in \mathcal{E}$$. I define a (global) threshold $$T$$ such that if $$w((u,v)) < T$$ the two vertices $$u,v \in \mathcal{V}$$ are in the same group: $$g \in \mathcal{V} \rightarrow \mathbb{Z}, g(v_1) = g(v_2)$$. This behaviour is transitive. The goal is to label the distinct groups starting from zero (the order of the groups is irrelevant). I know that this can be achieved trivially with BFS or DFS, but I want to avoid using those.

The idea I came up with is to iterate over the vertices, go over their 1-ring neighbourhood, and create a new group every time that $$w((u,v)) < T$$ for any of the edges and neither $$u$$ nor $$v$$ have been assigned a group (for example $$g(u) = g(v) = -1$$). Additionally, each group is assigned a label, which is initially equal to the index of the group: $$h:\mathbb{N} \rightarrow \mathbb{N}, h(g(u)) = g(u)$$. If at some point $$w((x,y)) < T$$ and $$w((y,z)) < T$$, but $$g(x) \ne g(z)$$ then set $$h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$$ and $$h(g(z)) \leftarrow h(g(x))$$. After this procedure it should hold: $$h(g(u))=h(g(v)), u,v \in \mathcal{V}$$ if there exists a path from $$u$$ to $$v$$: $$\pi = e_1,...,e_n$$ such that $$w(e_i) < T$$. Is the algorithm I came up with correct or did I miss something? As it is currently it requires $$|\mathcal{V}|$$ memory for each array $$g,h$$. Is there a way to optimize this further?

• This relationship is not transitive (contrary to what you wrote): if there is an edge $(a,b)$ with weight 3 and an edge $(b,c)$ with weight 3 and a threshold $T=4$, then your definition sets $a,b$ into the same group and $b,c$ into the same group but does not put $a,c$ into the same group. Can you clarify your problem statement?
– D.W.
Jul 11, 2020 at 18:28
• Your requirements are not clear. What's wrong with DFS? If you don't tell us why you rejected it, then I worry you might reject any other suggestions we might have too. If you rejected it probably there is some requirement you have that it does not meet; please take the opportunity to reflect on what that requirement might be.
– D.W.
Jul 11, 2020 at 18:29
• In the example you gave, $a$ and $c$ will be in the same group since there exists a path between $a$ and $c$ such that every edge on the path has a weight less than $T$. In fact thinking back on it, the problem formulation is equivalent to removing all edges with $w(e) \geq T$ and then finding all connected components of the new graph (which is a well-studied problem). I wanted to avoid DFS since I was thinking of the recursive formulation and wanted to avoid it. But I guess I can just rewrite it in an iterative fashion with an array of size $\mathcal{V}$ serving as stack, and an array of the Jul 11, 2020 at 20:42
• @D.W. groups that can double as "visited" vertices array. Ultimately it boils down to the same memory and runtime, but my previous algorithm would have required sorting at the end (since I wanted to re-enumerated groups from zero), while DFS doesn't. Anyways, your question was actually very helpful, since I guess sometimes a person just needs someone else to ask him a basic question to realize something obvious (the formulation with removed edges). Jul 11, 2020 at 20:46

As you highlight in your comments, a reasonable approach is to delete all edges with weight $$\ge T$$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).

I believe my algorithm is correct. A sketch of the proof is presented below:

There are 2 cases: either $$u \ne v \in \mathcal{V}$$ need to be from the same group, or they need to be from different groups (depending on whether there exists a path between them such that $$w(e) < T, \forall e \in \pi$$). It needs to be shown that the algorithm produces the resulting groups (the proof for each case will be done by contradiction).

1. Case 1: Let $$u,v \in \mathcal{V}$$ and there is a path from $$u$$ to $$v$$: $$\pi=e_1,...,e_n$$ such that $$w(e_i) < T$$. Then $$h(g(u))$$ should equal $$h(g(v))$$ for the algorithm to be correct.

2. Assumption of algorithm incorrectness: Assume that this is not the case, and that $$u$$, $$v$$ belong to different groups based on the result of the algorithm. For simplicity assume that $$\pi = \pi_1,x,y,z,\pi_2;\, x,y,z\in \mathcal{V}$$ such that all vertices from $$\pi_1,x$$ belong to $$h(g(u))$$ and all vertices on $$y,z,\pi_2$$ belong to $$h(g(v))$$ based on the algorithm. The case following the above assumption will be proven, but it should be clear that the same will hold by induction even if $$\pi$$ is split into more groups based on the algorithm.

Proof by contradiction: From (1), it follows $$w(x,y), and from (2) it follows: $$h(g(x)) \ne h(g(z))$$. From the definition of the algorithm it follows that it never splits groups, and it merges two groups if $$w(x,y) < T, w(y,z) but $$h(g(x)) \ne h(g(z))$$. Since the algorithm goes over all edges it should have merged $$h(g(x))$$ and $$h(g(z))$$.

1. Case 2: $$u,v \in \mathcal{V}$$ and there is no path $$\pi$$ from $$u$$ to $$v$$ such that $$w(e) < T, \forall e \in \pi$$, then $$h(g(u)) = h(g(v))$$.

2. Assumption of algorithm incorrectness: Assume $$h(g(u)) = h(g(v))$$.

Proof by contradiction: Both at group creation and at group merging (the only two ways for vertices to end up in the same group) there needs to exist a path between $$u$$ and $$v$$ such that $$w(e). (3) states that no such path exists, then $$h(g(u)) \ne h(g(v))$$.

Clearly the proof is fairly informal, so I may have missed something. I will leave the question open for a while, because 1) somebody may come up with a better & more optimized algoritm, and 2) I may have some mistake in my proof.