Breadth First Search Algorithm

bfs-algo.c

void visit( int k, int *id, int val[ ], nodePtr adjList[ ], Qptr q )‏
{
	nodePtr t;
	addQ(q, k);	//  add first to get started
	while ( ! emptyQ(q) )‏
	{
		k = getQ(q);	//  get front of queue and delete
		*id++;
		val[k] = *id;	//  k is visited
		t = adjList[k];
		while (t != NULL)‏
		{		//  all vertices adjacent to k are queued
			if (val[ t->v ] == 0)‏
			{
				addQ(q, t>v);	//  back of queue
				val[t->v] = -1;	//  mark as in queue
			}
			t = t -> next;
		}
	}
}

A graph traversal visits all vertices and edges.

Breadth First Search traverses a graph visiting each adjacent vertex, 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 adjacent vertex is visited.
Visiting all vertices completes the traversal.

Breadth First Search in an undirected graph can also be used to find
a spanning tree of a connected graph.

No backtracking is required. Each visited vertex is marked.
Starting at any vertex, each adjacent vertex is visited (level 1 vertices).
The adjacent vertices of each of these level 1 vertices are visited next
(level 2 vertices) unless they are marked as having been visited.

The traversal is complete on visiting all vertices.
At each vertex, adjacent vertices are visited in arbitrary order
(e.g. from right to left, etc.).