MST algorithm by picking minimum edge from each vertex?

0
votes

Is it possible to create an MST by simply iterating through vertices in a graph and selecting the smallest edge from that vertex and taking the union of all these edges? It seems this does not contradict the cut property and would be more efficient than implementing Prim's algorithm.

2
algorithmminimum-spanning-tree
how do you define smallest edge? the edge with least weight ? and can you use an example to show what you're referencing ? - Dhruv
Compare with en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm - mcdowella

2 Answers

0
votes

Kruskal's Algorithm for building a MST

  1. Initialize H = ∅.
  2. Sort edges in increasing order of weights.
  3. Loop through edges in increasing order of weights.
    • If endpoints of e are not connected in H.
      • Add e to H.

Source: https://www.cc.gatech.edu/~rpeng/CS3510_F17/Notes/Sep27MST.pdf

If you simply iterate over all the edges w/o taking into consideration if they are part of the MST, then you cannot be sure that they will not form a cycle.

0
votes

Nope. Vertexes can share a smallest edge, so you might not connect them all:

A---1---B
|       |
2       2
|       |
C---1---D

You need at least one of the weight 2 edges to make a MST, but neither of them is the smallest edge for any vertex.