patternModerate
If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?
Viewed 0 times
canedgesobtainallareequalbfsweightoneminimal
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#23179, answer score: 15
Revisions (0)
No revisions yet.