I need help in understanding how Kruskal\'s algorithm works. Specifically, for e

Question

I need help in understanding how Kruskal's algorithm works.

Specifically, for each line in the algorithm starting at the top, thanks, I have the algorithm below.

Also, there is an illustration of how it works, also pictured below. I just need help in tracing it and how it relates to the algorithm itself?

Thanks,

MG 0063.JPG a Search Kruskal's Algorithm Algorithm WC use. stoplile KRUSKAL(G, w) for each vertex v E G. V MAKE-SET (v) en sort the edges of G.E into nondecreasing order by weight w for each (u, v) taken from the sorted list if FIND-SET (u) FIND-SET (v) A U (u, v) a. we want a i UNION (u, v) m uand return A Running time?

Explanation / Answer

A simple concept of Kruskal Algorithm is:

1. Pick an edge with least weight in the graph such that adding this edge to MST doesn't lead to a cycle.

2. Mark both the vertices as visited, and add the edge to Minimum Spanning Tree(MST).

3. If all vertices are visited, and the tree is connected, stop, else go to step 1.

Its easy if you could sort the edges:

(g, h) = 1.

(c, i) = 2.

(f, g) = 2.

(a, b) = 4.

(c, f) = 4.

(g, i) = 6.

(c, d) = 7.

(h, i) = 7.

(a, h) = 8.

(b, c) = 8.

(d, e) = 9.

(e, f) = 10.

(b, h) = 11.

(d, f) = 14.

And now.

Figure (a), shows the first edge (g, h) is added to the MST.

Figure (b), shows the second edge (c, i) is added to the MST.

Figure (c), shows the third edge (f, g) is added to the MST.

Figure (d), shows the fourth edge (a, b) is added to the MST.

Figure (e), shows the fifth edge (c, f) is added to the MST.

Figure (f), shows the sixth edge (g, i) is not added to the MST, as that leads to a cycle.

Figure (g), shows the seventh edge (c, d) is added to the MST.

Figure (h), shows the seventh edge (h, i) is not added to the MST, as that leads to a cycle.

Figure (i), shows the eighth edge (a, h) is added to the MST.

Figure (j), shows the ninth edge (b, c) is not added to the MST, as that leads to a cycle.

Figure (k), shows the tenth edge (d, e) is added to the MST.

Figure (l), shows the eleventh edge (e, f) is not added to the MST, as that leads to a cycle.

Figure (m), shows the twelth edge (b, h) is not added to the MST, as that leads to a cycle.

Figure (n), shows the thirteenth edge (d, f) is not added to the MST, as that leads to a cycle.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.