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

Problem Detail: 

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?

Asked By : TheNotMe

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23179