Depth First Search Algorithm

dfs-algo.c

void visit( int k, int *id, int val[ ], nodePtr adjList[ ] )‏
{
	nodePtr t;
	*id++;
	val[k] = *id;
	t = adjList[k];
	while (t != NULL)‏
	{
		if (val[ t->v ] == 0)‏
			 visit(t->v, id, val, adjList);
		t = t -> next;
	}
}

void dfs( nodePtr adjList[ ], int n )‏
{
	int k, id;
	int val[1..MAX] = { 0 };
	id = 0;
	for (k = 0; k < n; k++)‏
		if (val(k) == 0)‏
			visit(k, &id, val, adjList);
}

A graph traversal visits all vertices and edges.

Depth First Search traverses a graph following each path, in turn, to reach a
dead-end vertex or an already-visited vertex, starting from an arbitrary vertex.
A dead-end vertex has only one edge or has all edges to already-visited vertices.
On reaching such a vertex, the next path from the previous vertex is traversed.
Returning to the starting vertex after all paths completes the traversal.

Depth First Search in an undirected graph can be used to
*Find a path from one vertex to another,
*Determine whether a graph is connected, and
*Find a spanning tree of a connected graph.

A backtracking algorithm attempts to follow each path. Each visited vertex
is marked. On reaching a vertex, which has no other edge or has already been
visited, i.e. marked (a dead-end), it backtracks to the previously-visited vertex and
follows another path and repeats the same process.
The traversal is complete on backtracking to the starting vertex from the final path.
At each vertex, paths are traversed in arbitrary order (e.g. from right to left, etc.).