-------------------------------------------------------------------------------
Depth First Search

Files:  dfs_bfs.c, dfs_bfs.h

This search starts at a vertex, v0, and proceeds by searching deeper into the
graph, until a dead end is reached, before attempting to follow sibling edges.
Visited vertices and traversed edges are kept track of so that the same vertex
is not visited twice.  The DFS algorithm can be implemented recursively, pseudo
code follows:

dfs(v)
{
    N[v] = c;  /* mark v visited by assigning it a visit number. */
    c++;
    for each w in OUT(v) {
        if N[w] == UNDEFINED {    /* N[w] == UNDEFINED means w is unvisited. */
            Add edge (v, w) to T;
            DFS(w);
        }
    }
}

main_program {

    T := EMPTY;  /* T is the tree made up of traversed edges. */
    c : = 0;     /* c is the counter for visit numbers. */
    for each vertex, v, in the graph,
        N[v] = UNDEFINED  /* Mark v "unvisited". */

    dfs(v0);  /* v0 is the starting vertex. */
}


This pseudo code, gives a basic DFS algorithm.  The algorithm structure for the
implementation in the source file dfs_bfs.h may differ from this slightly.
Note that in dfs_bfs.h, the function dfs() is available for other source files
to call.  A separate function, dfs_recursive(), performs the actual search.
This dfs_recursive() function accesses two global variables set up by dfs().
One points to the graph being searched, and the other points to the search
result structure.  When the search is complete, dfs() returns the search result
structure.

The result from the search represents edges in the tree, T, using two arrays,
parents[] and nodes[].  Both arrays are indexed by visit number, with
(parents[i], nodes[i]) representing the (i)th edge traversed.  The array N[]
in the above pseudo code corresponds to the visit_nos[] array in the source
file dfs_bfs.c.  The visit_nos[] array is indexed by vertex number, and stores
the visit number for each vertex.  This array is the inverse of the nodes[]
array.

The depth first search function makes use of directed graphs supplied by the
files dgraph.c and dgraph.h.  Note however that the edge cost in these graphs
is not needed, and ignored for depth first search.


-------------------------------------------------------------------------------
Breadth First Search

Files:  dfs_bfs.c, dfs_bfs.h

This search starts at a vertex, v0, and follows sibling edges before attempting
to proceed deeper into the graph.  Visited vertices and traversed edges are
kept track of so that the same vertex is not visited twice.  The BFS algorithm
is outlined in pseudo code below:

bfs(v)
{
    Q = {v};  /* Q is a queue, and initially contains only the stating vertex.
               */
    N[v] = c;  /* Mark v visited by assigning it a visit number. */
    c++;

    while Q is not empty {
        v <= Q;  /* Take the next item out the queue, and assign it to v. */

        for each w in OUT(v) {
            if N[w] == UNDEFINED {    /* If w is unvisited. */
                Add edge (v, w) to T;
                Q <= w;  /* Append w to the queue. */
                N[w] = c;  /* Mark w visited by assigning it a visit number.
                c++         */
            }
        }
    }
}

main_program {

    T := EMPTY;  /* T is the tree made up of traversed edges. */
    c : = 0;     /* c is the counter for visit numbers. */
    for each vertex, v, in the graph,
        N[v] = UNDEFINED  /* Mark v "unvisited". */

    bfs(v0);  /* v0 is the starting vertex. */
}

The bfs() function in the source file dfs_bfs.c gives an actual implementation
of breadth first search.  The algorithm structure in the actual implementation
may be slightly different from the above pseudo code.  Queue items are
represented by the dfs_queue_item_t structure type, which holds the vertex
number of the corresponding vertex.  The queue consists of a linked list of
these items.  As unvisited vertices are encountered, new queue items are added
to the tail of the linked list, and the next item at the head of the queue is
removed.  When the search is complete, bfs() returns a search result structure.

As with the dfs() function, the bfs() function uses graphs supplied by the
source files dgraph.c and dgraph.h.  Also, the same representation is used for
the search result.