Kruskal's algorithm for spanning tree
Another popular algorithm for finding a minimum spanning tree is Kruskal's algorithm. It is similar to Prim's algorithm and uses a greedy approach to find the solution. Here are the steps we need to implement Kruskal's algorithm:
- Create a forest T (a set of trees), where each vertex in the graph is a separate tree.
- Create a set S containing all the edges in the graph.
- While S is non-empty and T is not yet spanning:
1. Remove an edge with the minimum weight from S.
2. If that edge connects two different trees, then add it to the forest, combining two trees into a single tree; otherwise, discard that edge.
We will use the same graph that we used for Prim's algorithm. Here is the implementation of Kruskal's algorithm:
function Kruskal(array $graph): array { $len = count($graph); $tree = []; $set = []; foreach ($graph as $k => $adj) { $set[$k] = [$k]; } $edges = []; for ($i = 0; $i < $len; $i++) { for ($j ...