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)) &lt; 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)) &lt; 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)) &lt; T$ and $w((y,z)) &lt; 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) &lt; 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?
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).