9
$\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?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
15
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But, what about the contradicting example collapsar supplied? $\endgroup$
    – TheNotMe
    Mar 28, 2014 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, 2014 at 15:06
3
$\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.

Improve this answer
$\endgroup$
-3
$\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

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is not true. You can use Kruskal's algorithm. $\endgroup$
    – Evil
    Jan 3, 2019 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, 2019 at 4:03
  • $\begingroup$ It will pick one, anyone, it may as well randomly choose. $\endgroup$
    – Evil
    Jan 4, 2019 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, 2019 at 7:21
  • $\begingroup$ The question asked if we can use "BFS" and your answer just says "yes" without saying any more about why. We're not looking for answers that just claim the answer is yes. We're seeking answers that provide explanation, rationale, justification, or proof of their conclusion. I encourage you to edit your answer to explain why. Also, the question didn't ask "how can we do it", it asked if BFS works, so providing other algorithms doesn't answer the question that was asked. $\endgroup$
    – D.W. ♦
    Jan 27, 2020 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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