# If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time?

Intuitively this sounds correct, as BFS does not visit a node twice, and it only traverses from vertex $v$ to vertex $u$ iff it hasn't visited $u$ before, such that there aren't going to be any cycles, and if $G$ is connected it will eventually visit all nodes. Since the weight of all edges is equal, it doesn't matter which edges the BFS chose.

Does my reasoning make any sense?

-

If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.

-
But, what about the contradicting example collapsar supplied? –  TheNotMe Mar 28 '14 at 14:38
@TheNotMe BFS is usually referred to as a linear algorithm since it is $O(|V| + |E|)$. However, in the worst case (as in collapsar's example), $|E| = |V|^2$ so BFS can be thought of as $O(|V|^2)$. However, Prim's and Kruskal's algorithms for MSTs also contain $|E|$ in their time complexity, and are therefore not "linear" in collapsar's sense, either. What algorithm are you using as your benchmark? Does its time-complexity include $|E|$? If so, BFS is no worse than it. –  Patrick87 Mar 28 '14 at 15:06

If all edge costs are equal, then any spanning tree is also a minimum spanning tree. In this case, any algorithm that solves REACHABILITY solves MST as well.

Let S = {v0} be a set of nodes initially containing v0
Mark v0
Parent[v0] = -1
While S is not empty
Remove a vertex v from S
For all edges (v,u)
If u is unmarked
Mark it and add it to S
Parent[u] = v


You can recover the tree from the Parent relation. If S.Remove and S.Add take constant time, then the algorithm takes $\cal O(v+e)=\cal O(v^2)$ where $v,e$ are the number of vertices and edges.

-