Kruskal Algorithm
Make a minimal spanning tree by adding the smallest weight edge that connects two previously unconnected vertices. Count two vertices as connected if there is any path between them (not just a single edge).
Code Outline
We will produce a new Graph containing only the edges we select for the minimal spanning tree.
Consider each edge in the original graph, from the least weight to the
greatest. Add the edge (a,b) to your output graph if there is
currently no path from a to b in that graph.
Needed: a way to determine if there is a path from vertex a to
vertex b in the output graph.
Method 1: search every time
Determine if there is a path from a to b using only edges in the
allowed set. This could be a modification of the shortest
distances
function or you can write it from scratch.
def reachable(g_out: Graph, a: Vertex, b: Vertex) -> bool:
return false # write this
Method 2: lookup table of components
Modify your
connected_components function so that
it numbers the components it discovers. It then produces a map from
vertices to the component number.
def component_dict(g: Graph) -> Dict[Vertex, int]:
return {}
This method can be better than the previous one if you need to check many edges before you find one to add to your output edge set. It is also the basis for a more efficient idea.
Method 3: use a special data structure
Like method 2 but don’t re-create the dictionary every time.