一.图的深度优先搜索遍历（Depth First Search）
类似于二叉树的先序遍历。基本思想就是：首先访问出发点v（可以是任意的），并将其表记为已访问；然后选取与v邻接未被访问的任意一个顶点w，并访问他；再选取与w邻接的未被访问的任意一点并访问， 依次重复进行。 当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个重复上诉过程，直至所有顶点都被访问过为止。
下图表示遍历过程：红点表示已遍历过的
int visit[MAXNUM]; void Init_visit() { //初始化数组，使得数组每个元素都为0 for (int i = 0; i < MAXNUM; visit[i++] = 0); } void Visit(AdjListGraph *G, int v) { //访问操作 cout << G->adjlist[v].date << endl; } void DFS(AdjListGraph *G,int v) { ArcNode *p; visit[v] = 1; //置已访问 Visit(G, v); //访问操作 p = G->adjlist[v].firstarc;//p指向顶点v的第一条边 while (p != NULL) { if (visit[p->adjvex] == 0) //若定点未访问，则递归访问它 DFS(G, p->adjvex); p = p->next;//指向下一条边 } }
二.广度优先搜索遍历（Breadth-First Search）
类似与树的层次遍历。基本思想是：首先访问起始顶点v，然后选取与v邻接的全部顶点w1.....，wn进行访问，再依次访问与w1，...，wn邻接的全部顶点（已经访问的除外），依次类推，直到所有的点被访问完为止。
广度优先遍历的时候，需要用到一个队列（二叉树的层次遍历也要用到队列），算法执行过程可简单概括如下：
（1）.任取图中一个顶点访问，入队，并将这个顶点标记为已访问。
（2）.当队列不空的时候循环执行：出队，依次检查队列顶点所有邻接顶点，访问没有被访问过的邻接顶点并将其入队。
（3）.当队列为空的时候跳出循环，广度优先搜索完成。
过程大概如下图（从左到右，红点表示入队列了）：
代码如下：
/*Breadth-First Search*/ //visit数组元素全部初始化为0 void BFS(AdjListGraph *G, int v) { int que[MAXNUM], front = 0, rear = 0;//队列定义，数组，头指针，尾指针 int j; visit[v] = 1; //任意访问顶点v的函数 Visit(G, v); rear = (rear + 1) % MAXNUM; que[rear] = v; ArcNode *p; while (front != rear) { //队列为空时说明遍历完成 front = (front + 1) % MAXNUM; //顶点出队 j = que[front]; p = G->adjlist[j].firstarc;//p指向出队顶点的1第一条边 while (p != NULL) { //将p的所有邻接点中未被访问的入队 if (visit[p->adjvex] == 0) {//顶点未被访问则入队 visit[p->adjvex] = 1; Visit(G, p->adjvex); rear = (rear + 1) % MAXNUM;//该顶点入队 que[rear] = p->adjvex; } p = p->next;//p指向j的下一条边 } } } 三.非连通图遍历 以上两种遍历方法是针对连通图的。对于非连通图，只需啊哟将上述遍历函数放在一个循环中，循环用来检查图中每一个顶点，如果当前顶点没有被访问，则调用上述函数从这个顶点遍历，否则什么也不做。代码如下：
void dfs(AdjListGraph *G) { int i; for (i = 0; i < G->NumNodes; ++i) if (visit[i] == 0) DFS(G, i); } void bfs(AdjListGraph *G) { int i; for (i = 0; i < G->NumNodes; ++i) if (visit[i] == 0) BFS(G, i); }
