辅助队列的实现：

#ifndef QUEUE_H
#define QUEUE_H
#include "Graph.h"

typedef struct
{
	int *data;
	int head;
	int tail;
	int length;  // 现在数据长度
	int size;     //  总的可存储大小
}Queue;

void CreateQueue( Queue *Q, int s );

void EnQueue( Queue *Q, int x );

int DeQueue( Queue *Q );

#endif

#include "Queue.h"
#include <iostream>
using namespace std;

void CreateQueue( Queue *Q, int s )
{
	Q->size = s;
	Q->length = 0;
	Q->head = 0;
	Q->tail = 0;
	Q->data = new int[s];
}

void EnQueue( Queue *Q, int x )
{
	if ( ( Q->tail + 1 ) % Q->size == Q->head )
	{
		cout << "Overflow!" << endl;
		return;
	}
	Q->data[Q->tail] = x;
	Q->length++;
	Q->tail = ( Q->tail + 1 ) % Q->size;
}

int DeQueue( Queue *Q )
{
	if ( Q->tail == Q->head )
	{
		cout << "Underflow!" << endl;
		return -1;
	}
	int tmp = Q->data[Q->head];
	Q->head = ( Q->head + 1 + Q->size ) % Q->size;
	Q->length--;
	return tmp;
}

图的遍历头文件

/**
 * @brief Graph 
 * @author An
 * @data  2013.9.3                                                                  
**/
#ifndef GRAPH_H
#define GRAPH_H





enum Colour { WHITE, GRAY, BLACK };

// 邻接表的节点
struct EdgeNode
{
	int No;
	EdgeNode *nextEdge;

};

// 邻接表头结点
typedef struct VertexNode  
{
	int No;
	EdgeNode *firstEdge;

	Colour clr;
	int dist;
	VertexNode *parent;

	int start;
	int finish;
}*AdjList;

// 图
typedef struct 
{
	int vertexNum, edgeNum;
	AdjList *adjlist;
}ALGraph;


void CreateUDGraph( ALGraph *G, int vn, int en, int *v, int **e );

void CreateDGraph( ALGraph *G, int vn, int en, int *v, int **e );

void BFS( ALGraph *G, int index );

void PrintPath( ALGraph *G, int s, int v );

void DFSVisit( ALGraph *G, int index, int &time );

void DFS( ALGraph *G );

void PrintDFS( ALGraph *G );


#endif

源文件：

/**
 * @brief Graph 
 * @author An
 * @data  2013.9.3                                                                  
**/

#include "Graph.h"
#include "Queue.h"
#include <limits>
#include <iostream>
using namespace std;

void CreateUDGraph( ALGraph *G, int vn, int en, int *v, int **e )
{
	G->vertexNum = vn;
	G->edgeNum = en;

	// initialize the vertex
	G->adjlist = new VertexNode*[G->vertexNum];
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		G->adjlist[i] = new VertexNode[G->edgeNum];
	}
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		G->adjlist[i]->No = v[i];
		G->adjlist[i]->firstEdge = NULL;
	}

	// initialize the edge
	for ( int j = 0; j < G->edgeNum; ++j )
	{
		EdgeNode *node1 = new EdgeNode;
		EdgeNode *node2 = new EdgeNode;

		node1->No = e[j][1];
		node1->nextEdge = G->adjlist[e[j][0]]->firstEdge;
		G->adjlist[e[j][0]]->firstEdge = node1;

		node2->No = e[j][0];
		node2->nextEdge = G->adjlist[e[j][1]]->firstEdge;
		G->adjlist[e[j][1]]->firstEdge = node2;
	}

}

void CreateDGraph( ALGraph *G, int vn, int en, int *v, int **e )
{
	G->vertexNum = vn;
	G->edgeNum = en;

	// initialize the vertex
	G->adjlist = new VertexNode*[G->vertexNum];
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		G->adjlist[i] = new VertexNode[G->edgeNum];
	}
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		G->adjlist[i]->No = v[i];
		G->adjlist[i]->firstEdge = NULL;
	}

	// initialize the edge
	for ( int j = 0; j < G->edgeNum; ++j )
	{
		EdgeNode *node1 = new EdgeNode;

		node1->No = e[j][1];
		node1->nextEdge = G->adjlist[e[j][0]]->firstEdge;
		G->adjlist[e[j][0]]->firstEdge = node1;

	}
}

void BFS( ALGraph *G, int start )
{
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		if ( i != start )
		{
			G->adjlist[i]->clr = WHITE;
			G->adjlist[i]->dist = INT_MAX;
			G->adjlist[i]->parent = NULL;
		}
	}
	G->adjlist[start]->clr = GRAY;
	G->adjlist[start]->dist = 0;
	G->adjlist[start]->parent = NULL;

	Queue *Q = new Queue;
	CreateQueue( Q, G->vertexNum );
	for ( int i = -1; i < G->vertexNum; ++i ) // 考虑非连通情况
	{
		if ( G->adjlist[start]->clr == GRAY )
		{
			EnQueue( Q, start );
		}
		else if ( G->adjlist[i]->clr == WHITE )
		{
			G->adjlist[i]->clr = GRAY;
			EnQueue( Q, i );
		}
		
		while ( Q->length != 0 )
		{
			int u = DeQueue( Q );
			for ( EdgeNode *e = G->adjlist[u]->firstEdge; e != NULL; e = e->nextEdge )
			{
				if ( G->adjlist[e->No]->clr == WHITE )
				{
					G->adjlist[e->No]->clr = GRAY;
					G->adjlist[e->No]->dist = G->adjlist[u]->dist + 1;
					G->adjlist[e->No]->parent = G->adjlist[u];
					EnQueue( Q, e->No );
				}
			}
			G->adjlist[u]->clr = BLACK;
		}
	}

}

void PrintPath( ALGraph *G, int s, int v )
{
	if ( v == s )
	{
		cout << s;
	}
	else if ( G->adjlist[v]->parent == NULL )
	{
		cout << "no path from " << s << " to " << v << " exists." << endl;
	}
	else
	{
		PrintPath( G, s, G->adjlist[v]->parent->No );
		cout << " " << v;
	}

}


void DFSVisit( ALGraph *G, int index, int &time )
{
	cout << index << " ";
	G->adjlist[index]->clr = GRAY;
	time++;
	G->adjlist[index]->start = time;
	for ( EdgeNode *e = G->adjlist[index]->firstEdge; e != NULL; e = e->nextEdge )
	{
		if ( G->adjlist[e->No]->clr == WHITE )
		{
			G->adjlist[e->No]->parent == G->adjlist[index];
			DFSVisit( G, e->No, time );
		}
	}
	G->adjlist[index]->clr = BLACK;
	time++;
	G->adjlist[index]->finish = time;
}

void DFS( ALGraph *G )
{
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		G->adjlist[i]->clr = WHITE;
		G->adjlist[i]->parent = NULL;
	}
	int time = 0;
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		if ( G->adjlist[i]->clr == WHITE )
		{
			DFSVisit( G, i, time );
		}
	}
}

void PrintDFS( ALGraph *G )
{
	for ( int i = 0; i < G->vertexNum; ++i )
	{
		cout << i << " : " << G->adjlist[i]->start << ", " << G->adjlist[i]->finish << endl;
	}
}