Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
    
But, what about the contradicting example collapsar supplied? –  TheNotMe Mar 28 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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.