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?