Kruskal Algorithm
CS62, December, 2001
Question 4(b): Write Kruskal's Algorithm.
Answer: Kruskal's Algorithm enables us to find a minimal spanning tree T of a connected weighted graph G where n vertices. (In which case T must have n-1 edge.
Steps of Kruskal's Algorithm: The input is a connected weighted graph G wigh n vertices.
Step 1: Arrange the edges of G in order of increasing weights.
Step 2: Starting only with vertices of G and processing sequentially, add each edge which does not result in a cycle until n-1 edges are added.
Step 3: Exit
The algorithm is easily executed when graph G is small.
No comments:
Post a Comment