数据结构与算法18-图的遍历
从图中某一个顶点出发访遍图中其余顶点，且使每个顶点权被访问一次，这一过程就叫做图的遍历（Traversing Graph）。
深度优先遍历（Depth_First_Search）
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径想通的顶点都被访问到。
事实上，我们这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都补充访问到为止。
如果我们用的是邻接矩阵方式，则代码如下：
typedef int Boolean;
Boolean visited[MAX];
/*邻接矩阵的深度优先递归算法*/
void DFS(MGraph G,int i)
{
int j;
visited[i] = TRUE;
printf(“%c”,G.vexs[i]);
for(j=0;j<G.numVertexes;j++)
if(G.arc[i][j]==1 && !visited[j]) DFS(G,j); //对访问的邻接顶点递归调用。
}
/*邻接矩阵的深度遍历操作*/
void DFSTravese(MGraph G)
{
int i;
for(i=0;i<G.numVertexes;i++)
visited[i]=FALSE; //初始化访问状态为未访问
for(i=0;i<G.numVertexes;i++)
if(!visited[!])
DFS(G,i);
}
如果结构图是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成链表而不同
代码如下：
/*邻接链表的深度优先递归算法*/
void DFS(GrapAdjList GL,int i)
{
EdgeNode *p;
visited[i] = true;
printf(“%c”,GL->adjList[i].data); //打印顶点
p=GL->adjList[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
DFS(GL,p-adjvex);
p=p->next;
}
}
/*邻接表的深度遍历操作*/
void DFSTraverse(GraphAdjList GL)
{
int i;
for(i=0;i<GL->numVertexes;i++)
visited[i] = FALSE;
for(i=0;i<GL->numVertexes;i++)
if(!visited[i])
DFS(GL,i);
}
对比丙从此不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的怕有元素，因此需要O(n2)的时间。而邻接表做的存储结构时，找邻接点的所需的时间取决于顶点和边的数量，所以是O（n+e）显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而非言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。
广度优先遍历
又称为广度优先搜索，简称BFS。
如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历类似于树的层序遍历。
如图的图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与BF有边的顶点C、I、G、E为第三层，再将这四个顶点的边的D、H放在第四层
邻接矩阵的广度优先遍历算法
void SFSTraverse(MGraph G)
{
int i,j;
Queue Q;
for(i=0;i<G.numVertexes;i++)
visited[i] = FALSE;
InitQueue(&Q);
for(i=0;i<G.numVertexes;i++) //对第一个顶点做循环
{
if(!visited[i])
{
visited[i] = TRUE;
printf(“%c”,G.vexs[i]); //打印顶点，也可以其他操作
EnQueue(&Q,&i); //将此顶点入队列
while(!QueueEmpty(Q))
{
//队列不为空
DeQueue(&Q,&i); //待队中元素出队，赋值给i
for(j=0;j<G.numVertexes;j++)
{ //判断其它顶点和当前顶点存在边且未访问过
if(G.arc[i][j]==1 &&!visited[j])
{
visited[j] = TRUE;
printf(“%c”,G.vexs[j]);
EnQueue(&Q,j); //将找到的此顶点入队列
}
}
}
}
}
邻接表的广度遍历算法
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue Q;
for(i=0;i<GL->numVertexes;i++)
visited[i] = FALSE;
InitQueue(&Q);
for(i=0;i<GL->numVertexes;i++)
{
if(!visited[i])
{
visited[i]=TRUE;
printf(“%c”,GL->adjList[i].data);
EnQueue(&Q,i);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&i);
p=GL->adjList[i].firstedge; //找到当前顶点边表链表头指针
while(p)
{
if(!visited[p->adjvex])
{
visited[p->adjvex] = TRUE;
printf(“%c”,GL->adjList[p->adjvex].data);
EnQueue(&Q,p->adjvex);
}
p =p->next;
}
}
}
}
}
对比的图的深度优先遍历与广度优先遍历算法，你会发现，它们在时间复杂度上是一样的，不同之处仅仅在对于顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的，只是视不同的情况选择不同的算法。