ISE 390 -- Programming Challenges -- Week 8 Notes
This Weeks Goals:
To review the basic principles of graph algorithms and data
structures, specifically such basic applications of graph
traversal ("DFS") as connected components.
Business:
If you have not done so already email me a *single* attachment of
a Unix shar or tar or zip file with all your programs to date.
Feel free to add a README with any explanation you want. I definitely
want to see them this week.
Depth-First Search
DFS is essentially the same idea/algorithm as backtracking.
Both involve exhaustively searching all possibilities by advancing
if it is possible, and backing up soon as there is no unexplored
possibility for further advancement.
Both are perhaps most easily understood as recursive algorithms.
Rooted trees are a special type of graph (directed, acyclic,
in-degrees of at most 1, with an order defined on on the outgoing
edges of each node). In-order, pre-order, post-order, and pre-order
traversals are all basically DFS, differing only in how they use the
ordering of out-edges and when the process the vertex.
Applications of Depth-First 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.
(1) General traversal -- visit all vertices and edges. We can do
some processing step as we visit the edge or vertex (e.g. count
them, color them, copy them, etc.)
(2) Connected components -- a connected component of a graph is a
maximal set of vertices such that there is a path between every pair of
vertices. These are the separate `pieces' of the graph.
Connected components can easily be found using a minor variation
of depth-first search.
Data Structures for Graphs
Graphs can be represented as either adjacency matrices or adjacency
lists.
Matrices are simpler to code, but time and space inefficient for
sparse graphs. They should work fine if you have small graphs
(say <= 50 vertices)
Adjacency lists require pointers, but are not frightening if you
have used them before.
The following code fragments have been lifted from Sedgewick's "Algorithms
in C++" book:
/* Read a graph into an adjacency matrix */
int V, E;
int a[maxV][maxV];
void adjmatrix()
{
int j, x, y;
cin >> V >> E;
for (x = 1; x <= V; x++)
for (y = 1; y <= V; y++) a[x][y] = 0;
for (x = 1; x <= V; x++) a[x][x] = 1;
for (j = 1; j <= E; j++)
{
cin >> v1 >> v2;
x = index(v1); y = index(v2);
a[x][y] = 1; a[y][x] = 1;
}
}
/* 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;
}
}
/* DFS with adjacency lists and matrices */
void search()
{
int k;
for (k = 1; k <= V; k++) val[k] = unseen;
for (k = 1; k <= V; k++)
if (val[k] == unseen) visit(k);
}
void visit(int k) // DFS, adjacency lists
{
struct node *t;
val[k] = ++id;
for (t = adj[k]; t != z; t = t->next)
if (val[t->v] == unseen) visit(t->v);
}
void visit(int k) // DFS, adjacency matrix
{
int t;
val[k] = ++id;
for (t = 1; t <= V; t++)
if (a[k][t] != 0)
if (val[t] == unseen) visit(t);
}
Assigned Problems:
112 -- Find if there is a root to leaf path of a given weight.
This is a classic application of DFS. What information can you
pass up or down recursively so you can do the computation
in one pass?
168 -- Walk a path along a *directed* graph. Would an adjacency matrix suffice?
Would adjacency lists be easier?
193 -- This is not finding the two coloring with the largest number of
black nodes. It is maximum independent set in disguise!
Thus backtracking is needed..
315 -- Find the "articulation vertices" whose deletion disconnects the
graph. Can use do this using connected components?
352 -- Hunt for connected components in a grid. Should you explicitly
construct the graph, or is it easier to do DFS/BFS directly on
the matrix?