Minimum Spanning Tree

  • Let G=(V,E)G = (V, E) be an undirected graph.

    A spanning tree T=(V,F)T = (V, F) of GG is a graph containing the same vertices as GG, and V1|V| - 1 edges (called FF) of GG that form a tree. (There there is exactly one path between any two vertices of TT.)

    If GG is not connected, it has no spanning tree, but we can instead compute a spanning forest, or collection of spanning trees, having one tree for each connected component of GG.

  • If GG is weighted, then a minimum spanning tree TT of GG is a spanning tree of GG whose total weight (summed over all edges of TT) is minimal. In other words, no other spanning tree of GG has a smaller total weight.

Kruskal’s Algorithm

  • Kruskal’s algorithm computes the minimum spanning tree of GG as follows:

    • Create a new graph TT with the same vertices as GG, but no edges (yet).

    • Make a list of all the edges in GG.

    • Sort the edges by weight, from least to greatest.

    • Iterate through the edges in sorted order.

      For each edge (v,w)(v, w): if vv and ww are not connected by a path in T, add (v,w)(v, w) to TT.

  • Since Kruskal’s algorithm never adds (v,w)(v, w) if some other path already connects vv and ww, TT is guaranteed to be a tree (if GG is connected) or a forest (if GG is not).

  • Sorting the edges takes O(ElogE)O(|E| \log |E|) time. To determining whether two edges are already connected by a path, we can use disjoint sets, so that all the iterations of the look take less than O(ElogE)O(|E| \log |E|) time.

  • The running time of Kruskal’s algorithm is O(V+ElogE)O(|V| + |E| \log |E|) on adjacency lists and O(V2+ElogE)O(|V|^2 + |E| \log |E|) on adjacency matrix (it takes Θ(V2)\Theta(|V|^2) time to make a list of all the edges).

    Since we use adjacency lists when E<V2|E| < |V|^2, logE<2logV\log |E| < 2 \log |V|, so we can also say that the running time of Kruskal’s algorithm for adjacency lists is O(V+ElogV)O(|V| + |E| \log |V|).

  • Visualization:

Prim’s Algorithm

  • Prim’s algorithm computes the minimum spanning tree of GG as follows:

    • For all vv in VV, set v.distance=infv.distance = \inf, v.parent=nilv.parent = nil.

    • Create a new graph TT with the same vertices as GG, but no edges (yet).

    • Choose a vertex ss from VV. Set s.distance=0s.distance = 0.

    • Make a priority queue QQ of all the vertices, with distance as the priority.

    • While QQ is not empty:

      • v=Q.removeMinv = Q.removeMin

      • Add the edge (v,v.parent)(v, v.parent) to TT.

      • For each vertex ww such that e=(v,w)Ee = (v,w) \in E and wQw \in Q:

        if e.weight<w.distancee.weight < w.distance, set w.distance=e.weightw.distance = e.weight and w.parent=vw.parent = v.

  • We begin with a single root vertex rr, and add edges connecting new vertices until they are all connected. We’ll use a “distance” variable for each vertex to keep track of the shortest edge so far for joining that vertex to the result tree T. We’ll also track which edge that is.

  • The total time for V|V| removeMin operations will be in O(VlogV)O(|V| \log |V|). The total time for E|E| updatePriority operations will be in O(ElogV)O(|E| \log |V |). So the total running time is in O((V+E)logV)O((|V| + |E|) \log |V|), which is O(ElogV)O(|E| \log |V|).

  • Visualization:

results matching ""

    No results matching ""