Spanning Trees and Kruskal's Algorithm (AS)

Spanning Trees and Kruskal’s Algorithm (AS)

Spanning Trees and Kruskal’s Algorithm

Definition and Function

• Spanning Tree: A subgraph of a given graph which includes all the vertices and it’s a tree i.e., it has no cycles. A graph can have more than one spanning tree.

• Kruskal’s Algorithm: This is used to find the minimum spanning tree from a weighted graph. It is a greedy algorithm, as at each step it adds the cheapest unused edge to the spanning tree.

The Process of Kruskal’s Algorithm

• Step 1: Arrange all the edges in order of their weights in ascending order.

• Step 2: Add the smallest edge to the spanning tree. Make sure that the added edge does not form a cycle within the spanning tree.

• Step 3: Proceed by choosing the next smallest edge that doesn’t violate the property of the spanning tree. If it makes a cycle with the spanning tree, then reject the edge.

• Step 4: Repeat step 3, until all vertices are added to the spanning tree.

Key Concepts to Understand

• Greedy Algorithm: These types of algorithms make the optimal choice at each phase with the hope that these local choices lead to a global optimum. Kruskal’s Algorithm is a type of greedy algorithm.

• Cycle: Within the context of graphs, a cycle is a path of edges and vertices wherein a vertex is reachable from itself. In the process of using Kruskal’s Algorithm, students should ensure that no cycles are formed.

• Weight: The weight of an edge is a value, or ‘cost’ of traversal, that is associated with it. In the context of Kruskal’s Algorithm, the edge with the least weight is considered first.