Module 7: Graphs, Part I

Key ideas:

• Mark all vertices as "unvisited".
• Visit first vertex.
• Recursively visit its "unvisited" neighbors.

Example:

• Start with vertex 0 and mark it visited.

  

• Visit the first unvisited neighbor (node 1), mark it visited and recurse from there.

  

• Explore 1's first unvisited neighbor, 2.

  

• Continuing until all vertices are visited ...

  

  • Vertices are marked in order of visit.
  • An edge to an unvisited neighbor that gets visited next is in the depth-first search tree.

In-Class Exercise 7.10: What is the visit-order and depth-first search tree for this graph:

Then, apply breadth-first search, but using a stack instead of a queue. Show the stack contents.

Implementation:

• Easier than breadth-first search.

• Pseudocode: adjacency matrix

  
  Algorithm: depthFirstMatrix (adjMatrix, n)
  Input: A graph's adjacency matrix, number of vertices n.
  
       // Visit order will start with "0", so initialize to -1. 
  1.   for i=0 to n-1
  2.       visitOrder[i] = -1
  3.   endfor
  
       // A counter for the order: 
  4.   visitCount = -1
  
       // Look for an unvisited vertex and explore its tree. 
       // We need this because the graph may have multiple components. 
  5.   for i=0 to n-1
  6.       if visitOrder[i] < 0 
  7.         depthFirstMatrixRecursive (i)
  8.       endif
  9.   endfor
    

  
  Algorithm: depthFirstMatrixRecursive (v)
  Input: vertex v, adjMatrix is assumed to be global.
  
       // Mark vertex v as visited. 
  1.   visitCount = visitCount + 1
  2.   visitOrder[v] = visitCount
  
       // Look for first unvisited neighbor. 
  3.   for i=0 to n-1
  4.       if adjMatrix[v][i] > 0 and i != v  
  5.           if visitOrder[i] < 0
                   // If unvisited visit recursively. 
  6.               depthFirstMatrixRecursive (i)
  7.           endif
  8.       endif
  9.   endfor
    

• Completion order:
  • In breadth-first search, once a vertex is processed, it is never processed again.

  • In depth-first, we also encounter a vertex after returning from the recursive call.
    ⇒ we can record a completion order.

    

  • To record the completion order, simply increment the completion-counter after the recursion:

    
    Algorithm: depthFirstMatrixRecursive (v)
    Input: vertex v, adjMatrix is assumed to be global.
    
         // Mark vertex v as visited. 
    1.   visitCount = visitCount + 1
    2.   visitOrder[v] = visitCount
    
         // Look for first unvisited neighbor. 
    3.   for i=0 to n-1
    4.       if adjMatrix[v][i] > 0 and i != v  // Check self-loop. 
    5.           if visitOrder[i] < 0
                     // If unvisited visit recursively. 
    6.               depthFirstMatrixRecursive (i)
    7.           endif
    8.       endif
    9.   endfor
    
         // After returning from recursion, set completion order:     
    10.  completionCount = completionCount + 1
    11.  completionOrder[v] = completionCount
      

  • Note: completionCount and completionOrder need to be initialized (not shown) in depthFirstMatrix.

• Sample Java code: (source file)

  
  public class UndirectedDepthFirstMatrix {
  
    int numVertices;                 // Number of vertices, given as input. 
    int numEdges;                    // We keep track of the number of edges. 
    boolean isWeighted;              // Is this a weighted graph? 
    boolean useMatrix = true;        // Adjacency-matrix or list? 
    double [][] adjMatrix;           // The matrix. Note: we use "double" to store 
                                     // "double" weights, if the graph is weighted. 
  
    int[] visitOrder;                // visitOrder[i] = the i-th vertex to be visited in order. 
    int visitCount;                  // We will track visits with this counter. 
    int[] completionOrder;           // completionOrder[i] = the i-th vertex that completed. 
    int completionCount;             // For tracking. 
  
  
    public void initialize (int numVertices, boolean isWeighted)
    {
      // ... 
    }
  
  
    public void insertUndirectedEdge (int startVertex, int endVertex, double weight)
    {
      // ... 
    }
    
  
    //------------------------------------------------------------------------------- 
    // DEPTH-FIRST SEARCH 
  
    // Initialize visit information before search. 
  
    void initSearch ()
    {
      // IMPORTANT: all initializations will use "-1". We will test 
      // equality with "-1", so it's important not to change this cavalierly. 
      visitCount = -1;
      completionCount = -1;
      for (int i=0; i < numVertices; i++) {
        visitOrder[i] = -1;
        completionOrder[i] = -1;
      }
    }
  
  
    // Matrix implementation of depth-first search. 
  
    void depthFirstMatrix ()
    {
      // 1. Initialize visit variables (same initialization for breadth-first search). 
      initSearch ();
  
      // 2. Find an unvisited vertex and apply depth-first search to it. 
      //    Note: if the graph is connected, the call with i=0 will result 
      //          in visiting all vertices. Nonetheless, we don't know this  
      //          in advance, so we need to march through all the vertices. 
      for (int i=0; i < numVertices; i++) {
        if (visitOrder[i] < 0) {
          depthFirstMatrixRecursive (i);
        }
      }
    }
  
  
    // Recursive visiting of vertices starting from a vertex. 
  
    void depthFirstMatrixRecursive (int v)
    {
      // 1. First, visit the given vertex. Note: visitCount is a global. 
      visitCount++;
      visitOrder[v] = visitCount;
  
      // 2. Now find unvisited children and visit them recursively. 
      for (int i=0; i < numVertices; i++) {
  
        // 2.1  Check whether vertex i is a neighbor and avoid self-loops. 
        if ( (adjMatrix[v][i] > 0) && (i != v) ) {   
          if (visitOrder[i] == -1) {  
            // i is an unvisited neighbor. 
            depthFirstMatrixRecursive (i);
          }
        } 
      }
  
      // 3. After returning from recursion(s), set the post-order or "completion" order number. 
      completionCount++;
      completionOrder[v] = completionCount;
    }
  
  } // end-class 
    

"Back" and "Down" edges:

• Consider the previous example:

  

• Back edge
  • When vertex 2 probes neighbor 0, 0 has already been visited.
  • Vertex 0 is higher up in the tree (ancestor of 2)
    ⇒ 0 has a lower visitOrder
    ⇒ visitOrder[0] < visitOrder[2].
  • The exploration from 2 to 0 is called a back edge.

• Down edge:
  • When vertex 3 probes neighbor 6, 6 has already been visited.
  • Vertex 6 is lower down in the tree (descendant of 3)
    visitOrder[6] > visitOrder[3]
  • The exploration from 3 to 6 is called a down edge.

• Let's modify the code to detect back and down edges:

  
  Algorithm: depthFirstMatrixRecursive (v)
  Input: vertex v to be explored, adjMatrix is global.
  
       // Mark vertex v as visited. 
  1.   visitCount = visitCount + 1
  2.   visitOrder[v] = visitCount
  
       // Look for first unvisited neighbor. 
  3.   for i=0 to n-1
  4.       if adjMatrix[v][i] > 0 and i != v  // Check self-loop. 
  
  5.           if visitOrder[i] < 0
                   // If unvisited visit recursively. 
  6.               depthFirstMatrixRecursive (i)
  7.           else if (i != u)  // Avoid trivial case. 
  8.               if visitOrder[i] < visitOrder[v] 
                       // Found a back edge. 
  9.                   numBackEdges = numBackEdges + 1
  10.              else
                       // Found a down edge. 
  11.                  numDownEdges = numDownEdges + 1
  12.              endif
  13.          endif  // visitOrder < 0 
  
  14.       endif  // adjMatrix[v][i] > 0 
  15.   endfor
  
  
       // After returning from recursion, set completion order:     
  16.  completionCount = completionCount + 1
  17.  completionOrder[v] = completionCount
    

• Why identify back and down edges?
  • A graph with no back edges revealed by DFS is an acyclic graph.
  • Back and down edges are also useful in identifying so-called articulation edges (see below)

Identifying connected components:

• Depth-first search is most often used for identifying connected components in an undirected graph.

• Key ideas:
  • Every time depth-first is re-started (in depthFirstMatrix)
    a new component has been found.
    create a new component label.
  • In the recursion (depthFirstMatrixRecursive), simply identify each vertex with the current component label.

• Let's re-write (part of) the pseudocode to identify components:

  
  Algorithm: depthFirstMatrix (adjMatrix, n)
  Input: A graph's adjacency matrix, number of vertices n.
  
       // Visit order will start with "0", so initialize to -1. 
  1.   for i=0 to n-1
  2.       visitOrder[i] = -1
  3.   endfor
  
       // A counter for the order: 
  4.   visitCount = -1
  5.   completionCount = -1
  6.   currentComponentLabel = -1
  
       // Look for an unvisited vertex and explore its tree. 
       // We need this because the graph may have multiple components. 
  7.   for i=0 to n-1
  8.       if visitOrder[i] < 0 
  9.           currentComponentLabel = currentComponentLabel + 1
  10.          depthFirstMatrixRecursive (i)
  11.      endif
  12.  endfor
    

  
  Algorithm: depthFirstMatrixRecursive (v)
  Input: vertex v, adjMatrix is assumed to be global.
  
       // Mark vertex v as visited. 
  1.   visitCount = visitCount + 1
  2.   visitOrder[v] = visitCount
  
       // Mark the component label 
  3.   componentLabel[v] = currentComponentLabel
  
       // Look for first unvisited neighbor...  
  4.   // ... etc (same as earlier version) 
    

• Sample Java code: (source file).

In-Class Exercise 7.11: Trace the execution of DFS on the graph below to identify exactly when the components are identified and labeled.

Analysis: adjacency matrix

• Same as breadth-first search: O(V²)

• Why?
  • O(1) work for processing each vertex (except for identifying neighbors).
  • O(V) work for identifying neighbors.
    ⇒ O(V²) overall.

Analysis: adjacency list

• Similar analysis (to breadth-first search) gives: O(V + E).
• DFS with adjacency list is optimal.

Applications:

• Connectivity: identifying connected components.
  ⇒ which earlier-stated problem would this solve?

• Cycle existence.

• Others: finding articulation edges, vertices, "bipartiteness".

• Identifying equivalence classes

7.5   Finding Articulation Vertices using DFS

Algorithm: depthFirstMatrixRecursive (u, v)
//Note: u is the vertex from which we reach v
1.   visitOrder[v] = ++ visitCount
2.   minBackVisitOrder = visitOrder[v]

3.   for i=0 to n-1

4.       if i is a neighbor

5.           if visitOrder[i] < 0
6.               m = depthFirstMatrixRecursive (v, i)
7.               if m ≥ visitOrder[v]
8.                   print v                       // v is an articulation vertex
9.               endif
10.              if m < minBackVisitOrder
11.                  minBackVisitOrder = m
12.              endif

13.          else if (i != u)
14.              if visitOrder[i] < visitOrder[v]  // Found a back edge. 
15.                  if visitOrder[i] < minBackVisitOrder
                         minBackVisitOrder = visitOrder[i]
                     endif
16.              endif
17.          endif  // visitOrder < 0 

18.       endif  // i is a neighbor 

19.   endfor

20.  return minBackVisitOrder