刘凡 3282579ec1 first commit | 2 年之前 | |
---|---|---|
.. | ||
README.md | 2 年之前 | |
input.txt | 2 年之前 | |
kruskals_quick_union.py | 2 年之前 |
Input is taken from the file
Sample input
5
0 2 7 -1 -1
2 0 3 8 5
7 3 0 1 -1
-1 8 1 0 4
-1 5 -1 4 0
First line contains the number of nodes,say n.(Nodes are numbered as 0,1,2,...(n-1) ) Followed by n*n weighted matrix. Disconnected edges are represented by negative weight.
Graph is first drawn from the weighted matrix input from the user with weights shown. Edges are marked with black.
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected garph.
The algorithm operates by adding the egdes one by one in the order of their increasing lengths, so as to form a tree. Egdes are rejected if it's addition to the tree, forms a cycle. This continues till we have V-1 egdes in the tree. (V stands for the number of vertices).
To understand this better, consider the above input.
The graph, initially.
The smallest edge is of length 1, connecting Node 2 and Node 3. Since it is the first edge, it is added directly to the tree.
Next smallest edge is of length 2, connecting Node 0 and Node 1. Since it's addition doesn't result in a cycle, it is added to the tree.
Next smallest edge is of length 3, connecting Node 1 and Node 2. Since it's addition doesn't result in a cycle, it is added to the tree.
Next smallest edge is of length 4, connecting Node 3 and Node 4. Since it's addition doesn't result in a cycle, it is added to the tree.
Now we have 4 edges, hence we stop the iteration. Final graph, with red edges denoting the minimum spanning tree.
Time: O(V^2)
V - Number of vertices