Graph Visualization

Algorithm Log

# Prim's Algorithm
import heapq    # heapq is Python's min-priority queue implementation, we could do it without and use a for-loop to find the min cost edge

def prim(graph, start):
    mst = set()                 # Set to store edges (from, to, cost) of the MST
    visited = set([start])      # Set of vertices already included in MST
    
    # Edges list will act as a min-priority queue.
    # Stores tuples of (cost, from_node, to_node)
    # Initialize with edges from the starting node

    edges = []

    for to_node, cost in graph[start]:
        heapq.heappush(edges, (cost, start, to_node))

    while edges and len(mst) < len(graph) - 1:
        cost, frm, to = heapq.heappop(edges)        # Get the smallest edge

        if to not in visited:
            visited.add(to)
            mst.add((frm, to, cost))                # Add edge to MST

            # Add new candidate edges from the newly added 'to' node
            for to_next, cost_next in graph[to]:
                if to_next not in visited:
                    heapq.heappush(edges, (cost_next, to, to_next))
    return mst
                

# Kruskal's Algorithm
def kruskal(graph_nodes, graph_edges_list): # graph_nodes is list of V, graph_edges_list is list of (cost,u,v)
    parent = {}  # To store parent of each node for Union-Find

    # Helper for Union-Find: finds the representative (root) of a set
    def find(v):
        # Path compression: make every node on path point directly to root
        if parent[v] == v:
            return v
        parent[v] = find(parent[v])
        return parent[v]

    # Helper for Union-Find: unites two sets
    def union(u, v):
        root_u = find(u)
        root_v = find(v)
        if root_u == root_v: # If u and v are already in the same set
            return False # Cycle detected
        parent[root_u] = root_v # Merge sets by making one root parent of other
        return True

    mst = []
    
    # Initialize Union-Find: each node is its own parent initially
    for v in graph_nodes:
        parent[v] = v

    # Sort all edges by weight in non-decreasing order
    # graph_edges_list should be like: [(cost, u, v), (cost, u, v), ...]
    sorted_edges = sorted(graph_edges_list) 

    for cost, u, v in sorted_edges:
        if union(u, v): # If adding edge (u,v) doesn't form a cycle
            mst.append((u, v, cost))
            if len(mst) == len(graph_nodes) - 1: # MST is complete
                break
    
    return mst

# Example graph representation for Kruskal's input:
# nodes = ['A', 'B', 'C', 'D', 'E', 'F']
# edges_list = [
#   (3, 'A', 'B'), (5, 'A', 'F'), (6, 'A', 'E'),
#   (1, 'B', 'C'), (4, 'B', 'F'),
#   (4, 'C', 'F'), (6, 'C', 'D'),
#   (5, 'F', 'D'), (2, 'F', 'E')
# ]
# kruskal(nodes, edges_list)