## Lecture 27 - 03/22

### Graph Traversals

• Remember we had the following tree traversals: preorder, inorder, postorder, and level-order (like BFS)
• Similarly we have the following graph traversals:
• DFS Preorder - order by calls to recursive DFS algorithm
• DFS Postorder - order by returns from a recursive DFS algorithm
• Level-order/BFS search - order by increasing depth from starting node s
• Different types of traversals can be useful for different graph-related problems (such as map-coloring, etc...)
• Features of traversals:
• Ordering of vertices
• Information recorded as vertices are visited (such as marked and edgeTo from last time)
• Special actions to take on a visit (such as quit if at some goal vertex)
• Topological sort:
• Let's say we have a directed graph, where nodes are tasks and the edge directions indicate some order in which two tasks must be completed (some rule that A$A$ must be before B$B$)
• Valid ordering of the nodes/tasks in the graph is known as a topological sort; how do we find a valid ordering?
• Solution:
• Perform a DFS postorder search from every node of indegree 0 (every 'root' node on the graph), but don't clear marked between the postorders
• Record order of visitation from all of the postorders into a list sequentially (order of visitation from first postorder, followed by that of second, ...)
• This list will have a group of sequental values for each of the postorders searches done, where the order in each of the groups is from 'leaf' to 'root'
• Reverse this list; this will be a valid topological sort
• Note: instead of creating a list and reversing it, we can just use a stack instead
• Algorithm only has a solution if the graph has no cycles, which makes sense
• Can think of trying to find an order of vertices such that all the edges point to the right
• Implementation:
public class DepthFirstOrder {
private boolean[] marked;
private Stack<Integer> reversePostorder;  // use a stack instead of reversing a list
public DepthFirstOrder(DirGraph G) {
reversePostorder = new Stack<Integer>(); // create empty stack
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
dfs(G, v);  // Perform DFS Postorder of all unmarked vertices
// This is optimization over doing DFS at all indegree 0 vertices
// since we don't need to search for indegree 0 vertices with this
}
}
}
private void dfs(DirGraph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
reversePostorder.push(v); // Postorder: after each DFS completes, 'visit' vertex
}
public Iterable<Integer> reversePostorder() {
return reversePostorder; // LIFO order in stack takes care of reversing
}
}

• This is again Θ(V+E)$\Theta(V+E)$ runtime (running DFS over whole graph, so each edge is considered once, and each vertex no more than its indegree) and Θ(V)$\Theta(V)$ space
• We want to find the level-order traversal of the graph from a start vertex s
• We can do this by having a structure called a fringe that will hold vertices to be travelled to as we traverse
• For BFS, we use a queue (FIFO) fringe; for DFS, we use a stack (FILO) fringe, and for more complicated searches like A*/Djikstra's Algorithm (more on this in coming lectures), we use a priority queue fringe
• BFS search algorithm:
• Start the fringe with the starting vertex s, and mark it as visited
• Repeat until fringe empty:
• Pop vertex v from fringe (for a queue, this is the first element still in queue)
• Visit vertex v: add all unmarked vertices adjacent to v to the fringe, and mark them
• The order in which we remove elements from the fringe tells us the topological order, so if we want this order we can add the elements to a list as we visit vertices
• If we want to find the BFS connected paths between vertices from the starting node s, then have an edgeTo array that is updated on a vertex visit (similar to how we did this with DFS paths; implementation below):

public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
... // Other initialization/information to gather on node visits

private void bfs(Graph G, int s) {
Queue<Integer> fringe = new Queue<Integer>();
fringe.enqueue(s);
marked[s] = true;
while (!fringe.isEmpty()) {
int v = fringe.dequeue();
for (int w : G.adj(v)) {
if (!marked[w]) { // If w unvisited, visit it
fringe.enqueue(w); // Add it to the fringe
marked[w] = true;  // Mark it as visited
edgeTo[w] = v;     // Set it's edge to vertex v
}
}
}
}

• Runs in Θ(V+E)$\Theta(V+E)$ time and uses Θ(V)$\Theta(V)$ space:
• Each vertex and each edge are processed a constant number of times
• No vertex may be enqueued more than once
• Finds the shortest path
• Not going to be useful for an application like Google Maps
• We need to incorporate edge weights/importances (some edges/roads faster (better weighted) than others)
• When incorporating edge weights (so not all edges are of same importance), BFS is no longer optimal
• Solution: Djikstra's Algorithm (Uniform Cost Search(UCS)) / A*
• More on these search algorithms in coming lectures