Topological Sort and Graph Search

Read Bailey sections 16.4.1 and 16.4.2

Here is a video lecture for today's lesson.

The video contains sections on

1. Topological sort intro (0:25)
2. A first algorithm for topological sort (4:23)
3. Analyzing topological sort (9:31)
4. Dense vs sparse graphs (16:32)
5. Topological sort take 2 (20:27)
6. Graph traversal (25:02)
7. Breadth-first and depth-first search (35:18)
8. Shortest paths with BFS (40:20)
9. BFS vs DFS (46:50)
10. Shortest paths on a weighted graph (48:26)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=e61f48cb-f8d8-4b0c-9b06-acd9017bfa11

After this lesson you will be able to

1. Perform three classic graph algorithms: topological sort, breadth-first search, and depth-first search
2. Analyze the running time of graph algorithms

Problem: Given a DAG (directed acyclic graph) \(G=(V,E)\), output all vertices in an order such that no vertex appears before another vertex that has an edge to it.

Example input:

Example output: 111, 202, 201, 252, 304, 208, 251, 254, 320, 257, 231

• Why do we perform topological sorts only on DAGs?
  • Because a cycle means there is no correct answer
• Is there always a unique answer?
  • No, there can be 1 or more answers; depends on the graph

  • Graph with 5 topological orders:

    

• Do some DAGs have exactly 1 answer?
  • Yes, including all lists
• Uses:
  • Figuring out how to graduate
  • Computing an order in which to recompute cells in a spreadsheet
  • Determining an order to compile files using a Makefile
  • In general, taking a dependency graph and finding an order of execution
  • …

• Recall: In an undirected graph, \(0 \le |E| < |V|^2\)
• Recall: In a directed graph: \(0 \le |E| \le |V|^2\)
• So for any graph, \(O(|E|+|V|^2)\) is \(O(|V|^2)\)
• Another fact: If an undirected graph is connected, then \(|V|-1 \le |E|\)
• Because \(|E|\) is often much smaller than its maximum size, we do not always approximate \(|E|\) as \(O(|V|^2)\)
  • This is a technically correct upper bound, it just is often not tight (i.e., a lower upper bound would be more appropriate)
  • If it is tight, we say the graph is dense
    • Less precisely, dense means lots of edges
  • If \(|E|\) is \(O(|V|)\) we say the graph is sparse
    • Less precisely, sparse means most possible edges missing

So, the \(O(|V|^2)\) running time of our topological sort is fine for dense graphs, but poor performance for a sparse graph

• The trick is to avoid searching for a zero-degree node every time!
• Keep the pending zero-degree nodes in a list, stack, queue, or something
• Order we process them affects output but not correctness or efficiency provided add/remove are both \(O(1)\)

Using a queue:

1. Label each vertex with its in-degree, enqueue 0-degree nodes
2. While queue is not empty
   • v = queue.remove()
   • Output v and remove it from the graph
   • For each vertex u adjacent to v (i.e. u such that (v,u) in E), decrement the in-degree of u, if new degree is 0, add it to the queue

labelAllAndEnqueueZeros();
  for(ctr = 0; ctr < numVertices; ctr++){
  v = queue.remove();
  put v next in output
  for each w adjacent to v {
    w.indegree--;
    if (w.indegree == 0) 
      queue.add(v);
  }
}

• What is the worst-case running time?
  • Initialization: \(O(|V|+|E|)\)
  • Sum of all enqueues and dequeues: \(O(|V|)\)
  • Sum of all decrements: \(O(|E|)\)
  • So total is \(O(|V| + |E|)\) — much better for sparse graph!

• Next problem: For an arbitrary graph and a starting node \(v\), find all nodes reachable from \(v\) (i.e., there exists a path from \(v\))
  • Possibly do something for each node
  • Examples: print to output, set a field, etc.
• Basic idea:
  • Keep following nodes
  • But mark nodes after visiting them, so the traversal terminates and processes each reachable node exactly once

traverseGraph(Node start) {
  Set pending = emptySet()
  pending.add(start)
  mark start as visited
  while(pending is not empty) {
    next = pending.remove()
    for each node u adjacent to next
       if(u is not marked) {
         mark u
         pending.add(u)
       }
  }
}

• Assuming add and remove are \(O(1)\), entire traversal is \(O(|V| + |E|)\)
• The order we traverse depends entirely on \(add\) and \(remove\)
  • Popular choice: a stack depth-first graph search (DFS)
  • Popular choice: a queue breadth-first graph search (BFS)
• DFS and BFS are big ideas in computer science
  • Depth: recursively explore one part before going back to the other parts not yet explored
  • Breadth: explore areas closer to the start node first

1. Under what conditions is a topological sort of the vertices of a graph possible?
2. Implement a Java version of the breadth-first search pseudocode given above. It should be a method public int[] bfs(Graph G, int source) where Graph is the Graph class provided by algs4. In this class, ints are used to represent the vertices, so the source parameter is the vertex from which to begin the search. The method should return an array of integers of length G.V() (i.e., one entry for each vertex) where the entry at index i is the vertex that comes before vertex i on the shortest path from source. You will need a similar, separate array of booleans to keep track of which vertices the search has visited.
3. Is the depth-first search animation at https://visualgo.net/en/dfsbfs a recursive or stack-based implementation of DFS?

4. Give all possible topological sorts for the following graph:

   

• Summary
  • Topological sort takes a directed acyclic graph (DAG) and processes the nodes in an order that follows the dependency information encoded in the graph
    • Used a queue of pending nodes to efficiently implement the algorithm
  • Dense graph = lots of edges (\(|E|\) is \(O(|V|)\)), sparse graph = many potential edges missing (\(|E|\) is \(O(|V|)\))
  • Graph traversal similarly kept track of nodes to explore
    • Each time a node was removed from the set to explore, all of its unvisted neighbors were added
  • If we use a queue to hold the nodes to explore, we get breadth-first search
  • If we use a stack, we get depth-first search
  • Saw several examples of how these searches played out
  • Discussed how BFS can be used to find the shortest paths in a graph
• Questions?
• Form questions
• Go over bfs code
• Lab work time