- 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 must be beforeB ) - 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

- Perform a DFS postorder search from every node of indegree 0 (every 'root' node on the graph), but don't clear
- 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 listpublic DepthFirstOrder(DirGraph G) {reversePostorder = new Stack<Integer>(); // create empty stackmarked = 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) runtime (running DFS over whole graph, so each edge is considered once, and each vertex no more than its indegree) andΘ(V) space

- 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

- 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 visitsprivate 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 itfringe.enqueue(w); // Add it to the fringemarked[w] = true; // Mark it as visitededgeTo[w] = v; // Set it's edge to vertex v}}}}- Runs in
Θ(V+E) time and usesΘ(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