Kruskal and Prim

Understand the idea

Kruskal sorts edges and accepts those joining distinct DSU components. Prim grows one tree by selecting the cheapest edge crossing from chosen to unchosen vertices. The cut property justifies either choice.

Work through an example

For the weight-2,2,3 triangle, Kruskal accepts both 2 edges then rejects 3. Prim can start at any vertex and still obtain minimum total cost.

Time and space complexity

Kruskal O(E log E) plus DSU; heap Prim O(E log V) for standard adjacency implementations.

Why it works

Each selected safe edge can belong to some MST extending the current forest/tree.

Common mistakes

• Do not sort vertices instead of edges.
• Prim must ignore edges whose destination is already chosen.

Chapter lab · Python implementation

Weighted objectives require precise distinctions. Dijkstra finds cheapest routes from one source with nonnegative weights. Bellman-Ford permits negative edges and detects reachable negative cycles. A minimum spanning tree minimizes the total edges needed to connect all vertices; it does not minimize every source-to-vertex route.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

import heapq

def dijkstra(graph,start):
    if any(w<0 for edges in graph.values() for _,w in edges):
        raise ValueError('nonnegative weights required')
    distances={start:0}; heap=[(0,start)]
    while heap:
        cost,node=heapq.heappop(heap)
        if cost!=distances[node]: continue
        for neighbor,weight in graph.get(node,[]):
            candidate=cost+weight
            if candidate<distances.get(neighbor,float('inf')):
                distances[neighbor]=candidate
                heapq.heappush(heap,(candidate,neighbor))
    return distances

def bellman_ford(n,edges,start):
    d=[float('inf')]*n; d[start]=0
    for _ in range(n-1):
        changed=False
        for a,b,w in edges:
            if d[a]!=float('inf') and d[a]+w<d[b]:
                d[b]=d[a]+w; changed=True
        if not changed: break
    if any(d[a]!=float('inf') and d[a]+w<d[b] for a,b,w in edges):
        raise ValueError('reachable negative cycle')
    return d

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':[('B',4),('C',1)],'C':[('B',2)],'B':[]}
assert dijkstra(g,'A')=={'A':0,'B':3,'C':1}
assert bellman_ford(3,[(0,1,4),(0,2,1),(2,1,-2)],0)==[0,-1,1]
try: bellman_ford(2,[(0,1,-1),(1,0,-1)],0)
except ValueError: pass
else: raise AssertionError('negative cycle not detected')