Find the Minimal Spanning Tree for the following graph that would be output by K

Question

Find the Minimal Spanning Tree for the following graph that would be output by Kruskal's algorithm assuming that the edges are sorted in the following order.

(1,2), (5,6), (5,11), (6,11), (7,8), (7,12), (7,13), (8,12), (2,3), (3,13), (4,10), (6,7), (10,13), (12,13), (1,8), (3,4), (3,10), (8,13), (1,9), (1,13), (2,9), (4,5), (4,13), (9,13), (11,13), (2,13), (5,13), (6,13)

Find the Minimal Spanning Tree for the following graph that would be output by Kruskal's algorithm assuming that the edges are sorted in the following order. (1,2), (5,6), (5,11), (6,11), (7,8), (7,12), (7,13), (8,12), (2,3), (3,13), (4,10), (6,7), (10,13), (12,13), (1,8), (3,4), (3,10), (8,13), (1,9), (1,13), (2,9), (4,5), (4,13), (9,13), (11,13), (2,13), (5,13), (6,13)

Explanation / Answer

Kruskal's algorithm is greedy algorithm in graph theory.It is used to fing minimum spanning tree for a connected weighted graph.

There can be numerous answers to this question.Below I have explained my approach to the solution,which is also the safest and gets me the answer to kruskal's algorithm questions.

The two explicit conditions required for solution here is:

Start by connecting the minimum weight edges, remember the idea here is to involve all vertices.

Sume of all edges=20

There can be number of answers based on the which edges you connect.Above one is one of them.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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