How to Find an MST Using Kruskal's Algorithm

TL;DR

Kruskal's algorithm finds a minimum-cost spanning tree by considering edges in increasing order of weight and accepting an edge only when it does not create a cycle. Stop when the tree contains N-1 edges; the demonstrated graph has 7 vertices, uses 6 selected edges, and produces a minimum total cost of 21.

Transcript

Hello friends, welcome to Gate Smashers In this video we are going to discuss about Kruskal algorithm And in this video we are going to discuss all important points related to Kruskal algorithm Which will be very beneficial for your competitive exams, even college and university level exams So guys, like this video quickly, subscribe the ch... Read More

Key Insights

• A spanning tree preserves the same number of vertices as the original graph. In the demonstrated graph, all 7 vertices must appear in the final spanning tree, so the algorithm cannot omit a vertex even when choosing the lowest-cost edges.
• A spanning tree with N vertices contains N-1 edges. Because the example has 7 vertices, Kruskal's algorithm stops after selecting 6 valid edges that connect the graph without producing a cycle.
• Kruskal's algorithm processes edges in increasing order of weight. The example starts with the B-to-E edge of weight 2, then considers edges of weight 3, followed by edges of weight 4 and 5.
• Cycle prevention is mandatory when selecting an edge. An edge must be rejected even when its weight is currently minimal if adding it would create a cycle, because a structure containing a cycle is not a tree.
• Equal-weight edges may be processed in different orders. When several edges have weight 4, any can be considered first, but the selected combination must remain cycle-free and eventually connect every vertex.
• Kruskal's intermediate result may be disconnected. Separate groups such as A-to-C and B-to-E can exist while processing edges, but the completed minimum spanning tree must be connected after N-1 valid edges have been accepted.
• The demonstrated minimum spanning tree has a total cost of 21. Its 6 accepted edge weights are 2, 3, 3, 4, 4, and 5, while edges that would create cycles are excluded.
• A MinHeap implementation can construct the heap from E edges in order E time with heapify. Repeated edge removal costs log E, producing order N log E in the stated best case and order E log E in the worst case.

Questions & Answers

Q: How does Kruskal's algorithm find a minimum spanning tree?

Kruskal's algorithm first arranges all graph edges in increasing order of weight. It considers the smallest available edge and adds it to the developing spanning tree only if that edge does not create a cycle. This process continues through progressively larger weights until exactly N-1 edges have been accepted and all original vertices are connected.

Q: What properties must a spanning tree satisfy?

A spanning tree must contain the same vertices as the original graph, remain free of cycles, and be connected when complete. If the graph has N vertices, the spanning tree must contain N-1 edges. For the demonstrated graph with 7 vertices, a valid spanning tree therefore contains all 7 vertices and exactly 6 selected edges.

Q: Why are some low-weight edges rejected by Kruskal's algorithm?

A low-weight edge is rejected when adding it would produce a cycle among vertices that are already connected through selected edges. In the example, the F-to-G edge of weight 4 can be excluded after other edges connect that region, and the A-to-B edge of weight 5 is rejected because it would create the A-B-C cycle.

Q: Can Kruskal's intermediate spanning forest be disconnected?

Kruskal's intermediate result can be disconnected because the algorithm selects globally light edges wherever they appear in the graph. For example, A-to-C may form one component while B-to-E and E-to-F form another. These separate parts are acceptable during execution, but they must become connected when the final N-1 edges have been selected.

Q: What happens when several edges have the same weight?

When several edges share the same weight, Kruskal's algorithm may consider them in any order. The order itself does not matter in the demonstrated procedure, provided every accepted edge avoids creating a cycle. If selecting one equal-weight edge makes another produce a cycle, the latter edge is rejected and the cycle-free choice is retained.

Q: When should Kruskal's algorithm stop selecting edges?

Kruskal's algorithm stops when the developing spanning tree contains N-1 accepted edges. The example graph contains 7 vertices, so the completed answer requires 6 edges. Once those 6 edges connect all vertices without a cycle, the spanning tree is complete and no additional edge should be added, even if more graph edges remain.

Q: What is the minimum spanning tree cost in the example?

The minimum spanning tree shown in the example has a total cost of 21. The 6 accepted edges have weights 2, 3, 3, 4, 4, and 5. Adding these values gives 21. Kruskal's algorithm and Prim's algorithm produce the same minimum cost for this example, although their construction methods differ.

Q: What is the time complexity of Kruskal's algorithm with a MinHeap?

The stated MinHeap approach builds a heap from E edges in order E time when heapify is used. Removing and rearranging the heap for each considered edge costs log E. The stated best case processes N-1 edges and is written as order N log E, while the worst case examines all edges and takes order E log E.

Summary & Key Takeaways

• Kruskal's algorithm constructs a minimum-cost spanning tree for a weighted graph. The resulting tree retains every vertex from the original graph, contains exactly N-1 edges, remains connected when complete, and contains no cycle. Kruskal and Prim produce the same minimum cost, although they build their answers through different procedures.

• The practical method begins by arranging all weighted edges in increasing order. Examine the smallest available edge, add it when it does not form a cycle, and reject it otherwise. Equal-weight edges may be considered in different orders. Continue until N-1 acceptable edges have been selected for the completed spanning tree.

• The example begins with 7 vertices and therefore requires 6 selected edges. Edges with weights 2, 3, 3, 4, 4, and 5 form the demonstrated answer, while other edges are rejected for creating cycles. Their combined cost is 21. A MinHeap implementation has worst-case complexity of order E log E.