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.