minimum spanning tree kruskal Algorithm
The Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of an undirected, weighted graph. The minimum spanning tree is a tree that connects all the vertices in the graph with the minimum possible total edge weights. Kruskal's algorithm works by sorting all the edges in the graph based on their weights and then iteratively adding the smallest edge that does not form a cycle with the existing edges in the MST. The algorithm continues until all the vertices are connected or the MST is formed.
To implement Kruskal's algorithm, first, sort all the edges in the graph in non-decreasing order of their weights. Then, initialize an empty set to store the MST edges and a disjoint-set data structure to keep track of connected components. Iterate through the sorted edges list, and for each edge, check if the two vertices it connects belong to the same connected component or not. If the vertices belong to different components, add the edge to the MST set and merge the two components in the disjoint-set data structure. Continue this process until all the vertices are connected or the MST is formed. Kruskal's algorithm has a time complexity of O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices in the graph.
if __name__ == "__main__":
num_nodes, num_edges = list(map(int, input().strip().split()))
edges = []
for i in range(num_edges):
node1, node2, cost = list(map(int, input().strip().split()))
edges.append((i, node1, node2, cost))
edges = sorted(edges, key=lambda edge: edge[3])
parent = list(range(num_nodes))
def find_parent(i):
if i != parent[i]:
parent[i] = find_parent(parent[i])
return parent[i]
minimum_spanning_tree_cost = 0
minimum_spanning_tree = []
for edge in edges:
parent_a = find_parent(edge[1])
parent_b = find_parent(edge[2])
if parent_a != parent_b:
minimum_spanning_tree_cost += edge[3]
minimum_spanning_tree.append(edge)
parent[parent_a] = parent_b
print(minimum_spanning_tree_cost)
for edge in minimum_spanning_tree:
print(edge)
