7
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But, what about the contradicting example collapsar supplied? $\endgroup$ – TheNotMe Mar 28 '14 at 14:38
  • $\begingroup$ @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. $\endgroup$ – Patrick87 Mar 28 '14 at 15:06
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

If all the edges are of equal weight we can use:

-BFS -DFS -Dijkstra's algorithm -Prim's algorithm

But you cannot use

-kruskal's algorithm

$\endgroup$
  • $\begingroup$ This is not true. You can use Kruskal's algorithm. $\endgroup$ – Evil Jan 3 at 5:55
  • $\begingroup$ How is it possible because it will end up giving all the edges as we start from the least weight first !! $\endgroup$ – Nandkishor Nangre Jan 4 at 4:03
  • $\begingroup$ It will pick one, anyone, it may as well randomly choose. $\endgroup$ – Evil Jan 4 at 4:34
  • $\begingroup$ Yeah I got ur point !! but is it applicable in kruskal algo.... because I have never seen any code of kruskal stating the above phenomenon $\endgroup$ – Nandkishor Nangre Jan 4 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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