Kruskal's Algorithm

 Kruskal's Algorithm

Kruskal's algorithm is a minimum spanning tree algorithm that finds the minimum spanning tree for a connected weighted graph. It starts with the edges with the lowest weights and keeps adding edges until all vertices are connected.

python

# Kruskal's algorithm function

def kruskal(graph):

    parent = {node: node for node in graph}

    minimum_spanning_tree = set()

    edges = [(weight, node, neighbor) for node in graph for neighbor, weight in graph[node].items()]

    edges.sort()

    for weight, node, neighbor in edges:

        root_node = find(node, parent)

        root_neighbor = find(neighbor, parent)

        if root_node != root_neighbor:

            minimum_spanning_tree.add((node, neighbor, weight))

            parent[root_node] = root_neighbor

    return minimum_spanning_tree

def find(node, parent):

    while parent[node] != node:

        node = parent[node]

    return node