ISE 390 -- Programming Challenges -- Week 9 Notes This Weeks Goals: To review the basic principles of graph algorithms and data structures, specifically path based problems such as breadth-first-search and shortest path. Breadth-First Search BFS is essentially the same idea/algorithm as DFS, except that the next node to explore is pulled off a queue instead of a stack. Thus the nodes are accessed in a first-in-first-out order. BFS builds a tree from the root node representing the minimum number of edges it takes to get from the root to every other vertex. Note that this gives the shortest path in the graph *only* if the graphs unweighted. Applications of BFS/DFS Search Note that breadth-first search (BFS) will also work for some of these, but not others. As we will see, BFS is appropriate (1) if all we care about is visiting all vertices and edges of the graph, and don't care about order, or (2) we are interested in shortest paths on unweighted graphs. Important Graph Algorithms (1) Shortest paths in unweighted graphs -- do BFS (2) Shortest paths in weighted graphs -- BFS does not work. Do Dijkstra's algorithm or Floyd-Warshall ShortestPath-Dijkstra($G,s,t$) $known = \{s\}$ for $i=1$ to $n$, $dist[i]=\infty$ for each edge $(s, v)$, $dist[v]=w(s, v)$ $last=s$ while ($last \neq t$) select $v_{next}$, the unknown vertex minimizing $dist[v]$ for each edge $(v_{next},x)$, $dist[x]=\min[dist[x], dist[v_{next}]+w(v_{next},x)]$ $last=v_{next}$ $known = known \cup \{v_{next}\}$ (2) Topological sorting -- order the vertices from 1 to n such that all directed edges go from left to right; thus we can process each node before any of its predecessors. Topological sort algorithm: any node of indegree 0 can be first; deleting it must leave another such node. (3) Strongly connected components -- partition the graph into chunks such that there are directed paths between all pairs of vertices within a chunk. Strong components algorithm -- use DFS to find a directed cycle in the graph (any back edge plus the down path in the DFS tree gives a cycle). All vertices in this cycle are in a component. Shrink these to a vertex and repeat. (4) Minimum spanning trees -- connect the vertices by the smallest amount of wire, roadway, or edge weight. The two main algorithms are Kruskal's and Prim's Prim-MST(G) Select an arbitrary vertex $s$ to start the tree from. While (there are still nontree vertices) Select the edge of minimum weight between a tree and nontree vertex Add the selected edge and vertex to the tree $T_{prim}$. The following code fragments have been lifted from Sedgewick's "Algorithms in C++" book: /* Read a graph into an adjacency list */ struct node { int v; struct node *next; }; int V, E; struct node *adj[maxV], *z; void adjlist() { int j, x, y; struct node *t; cin >> V >> E; z = new node; z->next = z; for (j = 1; j <= V; j++) adj[j] = z; for (j = 1; j <= E; j++) { cin >> v1 >> v2; x = index(v1); y = index(v2); t = new node; t->v = x; t->next = adj[y]; adj[y] = t; t = new node; t->v = y; t->next = adj[x]; adj[x] = t; } } Queue queue(maxV); void visit(int k) // BFS, adjacency lists { struct node *t; queue.put(k); while (!queue.empty()) { k = queue.get(); val[k] = ++id; for (t = adj[k]; t != z; t = t->next) if (val[t->v] == unseen) { queue.put(t->v); val[t->v] = -1; } } } /* BFS with adjacency lists */ void search() { int k; queue.init() for (k = 1; k <= V; k++) val[k] = unseen; for (k = 1; k <= V; k++) if (val[k] == unseen) visit(k); } /* Floyd-Warshall Algorithm to find all-pairs shortest path */ for (y = 1; y <= V; y++) for (x = 1; x <= V; x++) if (a[x][y]) for (j = 1; j <= V; j++) if (a[y][j] > 0) if (!a[x][j] || (a[x][y]+a[y][j] < a[x][j])) a[x][j] = a[x][y] + a[y][j]; Assigned Problems: 157 -- Find the shortest path in a transportation graph. Some syntactic complications since the graph is specified in a non-standard fashion (as the union of "lines") 196 -- Implement a simple spreadsheet program. Topological sorting of the formula cell graph is necessary to do it "right", although there may be a simple hack based on knowing the maximum number of cells and the acyclicity of the graph. 336 -- Find the nodes reachable in a given number of hops from the source. Is this a weighted or unweighted graph, and what does that mean? 314 -- Plot the motion of the robot where it costs time to turn and there are obstacles on the grid. How do we modify Dijkstra's algorithm for turn costs? 318 -- Given a graph of domino paths, figure out where the last domino will fall. This is a BFS/shortest path type problem, where the goal is to visit every edge in a reasonable order.