CmSc 250 Intro to Algorithms


Graph Algorithms - Minimum Spanning Tree

  1. Spanning trees
  2. Spanning tree in unweighted graphs
  3. Minimum spanning tree in weighted graphs - Prim's algorithm
  4. Minimum spanning tree in weighted graphs - Kruskal's algorithm
  5. Discussion

Animation

Learning Goals
Exam-like questions


  1. Spanning trees

  2. Spanning tree: a tree that contains all vertices in the graph.
    The concept is relevant to connected undirected graphs.

    Number of nodes in the spanning tree: |V|
    Number of edges in the spanning tree: |V|-1

    If the graph is unweighted any spanning tree will have same number of edges. That is why it is not called "minimum" - all spanning trees will be 'minimum' trees with number of edges equal to |V|-1.

    If the graph is weighted then we are interested in finding a tree with a minimum total sum of the edge weights.

  3. Spanning tree in unweighted graphs

  4. Algorithm to find a spanning tree (similar to finding the shortest path in unweighted graphs)

    Data structures needed:

    A table (an array) T with size = number of vertices, where Ti = parent of vertex vi
    Adjacency lists
    A queue of vertices to be processed
    A counter to count the number of vertices included in the tree

    1. Choose a vertex u and store it in the queue.
      Set a counter = 0 , and Tu = r
      (u would be the root of the tree)
    2. While the queue is not empty and counter < |V| -1 do the following:
      1. Read a vertex vj from the queue.
      2. For all uk in the adjacency list of vj do the following
      3. If Tk is empty,
        Tk = vj (the parent of uk is vj)
        counter = counter + 1
        store uk in the queue

    Example: the "prisoners" problem

    Complexity: O(|E| + |V|)

    We store in the queue each vertex only once (O(|V|)).
    In step 2b. we examine the outgoing edges for a given vertex, thus the sum of all examined edges in the while loop will be equal to the the number of all edges - (O(|E|)).

    If we use matrix representation the complexity is O(|V|2),
    because we need to read an entire row in the matrix of length |V| in order
    to find the adjecent vertices for a given vertex.

  5. Minimum spanning tree in weighted graphs - Prim's algorithm

  6. Problem: For a given weighted graph, find a spanning tree with the minimal sum of the weights.

    The algorithm is similar to finding the shortest paths in a weighted graphs.
    The difference is that we record in the table the length of the current edge, not the length of the path .

    Data structures needed:

    • A table T with number of rows = number of vertices, and three columns:
      Ti,1 = True if the vertex has been fixed in the tree, False otherwise. This is necessary because the graph is not directed and without this information we may enter a cycle.
      Ti,2 = the length of the edge from the chosen parent (stored in the third column of the table) to the vertex vi,
      Ti,3 = parent of vertex vi
    • Adjacency lists
    • A priority queue of vertices to be processed.
      The priority of each vertex is determined by the weight of edge that links the vertex to its parent. The priority may change if we change the parent.

    Algorithm:

    1. Initialize first column to False, select a vertex s and store it in the priority queue
      with priority = 0, set Ts,2 = 0, Ts,3 = root
      (It does not matter which vertex is chosen, because all vertices have to be in the tree.)

    2. While there are vertices in the queue:
      1. DeleteMin a vertex v from the queue and set Tv,1 = True
      2. For all adjacent vertices w:
        • If Tw,1 = T do nothing
        • If Tw,2 is empty:
          • Tw,2 = weight of edge (v,w) (stored in the adjacency list)
          • Tw,3 = v (this is the parent)
          • append w in the queue with priority = weight of (v,w)
        • If Tw,2 > weight of (v,w)
          • Update Tw,2 = weight of edge (v,w)
          • Update the priority of w (this is done by updating the priority of an element in the queue - decreaseKey operation. Complexity O(logV))
          • Update Tw,3 = v

    At the end of the algorithm, the tree would be represented in the table with its edges

    {(Ti,3 , vi ) | i = 1, 2, -|V|}

    Complexity: O(| E |log(| V |))
    All edges have to be examined, and in the worst case each edge might cause updating of the priority queue.

    If adjacency matrix is used, the complexity would increase to O(|V|2)

    Example: The "conspirators" problem

  7. Minimum spanning tree in weighted graphs - Kruskal's algorithm

  8. Kruskal's algorithm works with tree forests and the set of edges.

    Algorithm:

    1. Initially we build |V| trees consisting of one vertex only - each vertex is a tree of its own.
      The edges are stored in a priority queue with priority - the weight.

    2. While the number of distinct trees is greater than one:
    3. DeleteMin an edge (u,v) from the priority queue.
      1. If u and v belong to one and the same tree, do nothing.
      2. If u and v belong to different trees, link the trees by the edge

    Implementation

    The algorithm is implemented using operations on disjoint sets.
    All the vertices are grouped into sets corresponding to the currently built trees.
    Since each vertex appears in one tree only, the sets are disjoint.

    Two set operations are used:

    1. comparison:
    2. Each vertex is associated with the disjoint set where it belongs.
      To find out whether two vertices are in the same tree,
      we need to find out if their disjoint sets are the same.

    3. union:
    4. When we link the trees, the combine the two disjoint sets to form one set
      - corresponding to the new tree

    Example: The "conspirators" problem

    Complexity of Kruskal's algorithm:

    A detailed analysis will show O(|V|) + O(|E|log(|E|)) + O(|E|log(|V|)).
    1. We need O(|V|) operations to build the initial forest with |V| trees each containing one node.
    2. The edges are stored in a priority queue and each time the smallest edge is retrieved, hence we need O(|E|log(|E|)) operations to process the edges.
    3. Finally, the disjoint set operations are implemented by a tree with |V| nodes,
      hence we need O(|E|log(|V|)) operations (a comparison is performed for each edge in the worst case).

    Disregarding the lower term O(|V|) we get O(|E|(log(|V|) + log(|E|)).
    At the worst case |E| = O(|V|2). Hence log(|E|) = O(log(|V|2)) = O(2log(|V|)) = O(log(|V|).
    Thus we get complexity O(|E|log(|V|)).

    On the other hand, |V| = O(|E|), hence we can reduce the complexity expression to O(|E|log(|E|)).

  9. Discussion

  10. For sparse trees Kruskal's algorithm is better - since it is guided by the edges.

    For dense trees Prim's algorithm is better - the process is limited by the number of the vertices in the graph.


Learning Goals

  • Be able to explain the spanning tree algorithm for unweighted graphs.
  • Be able to explain Prim's miminum spanning tree algorithm for weighted graphs.
  • Be able to explain the basic idea of Kruskal's miminum spanning tree algorithm for weighted graphs.
  • Be able to run the algorithms on paper.

Exam-like questions

  1. Explain the spanning tree algorithm for unweighted graphs.
  2. What is the complexity of the spanning tree algorithm for unweighted graphs? Explain your answer.
  3. Explain Prim's algorithm for mimimal spanning trees.
  4. What is the complexity of Prim's algorithm? Explain your answer.
  5. Explain the basic idea of Kruskal's algorithm for mimimal spanning trees.
  6. What is the complexity of Kruskal's algorithm? Explain your answer.
  7. Given a weighted graph with 100 vertices and 200 edges, which algorithm would be preferred to find the minimum spanning tree? Explain your answer.
  8. Given a weighted graph with 100 vertices and 80000 edges, which algorithm would be preferred to find the minimum spanning tree? Explain your answer.
  9. Given a unweighted graph and a vertex, find a spanning tree (run the algorithm on paper)
  10. Given a weighted graph, find the minimum spanning tree using Prim's algorithm
    (run the algorithm on paper)
  11. Given a weighted graph, find the minimum spanning tree using Kruskal's algorithm
    (run the algorithm on paper)

Back to Contents page
Created by Lydia Sinapova