给定一个图G=(V,E)和V(G)中的任一顶点v，从v出发，访问G中的所有顶点。当G是连通图时，则从v出发，顺着G中的边可以访问该图中的所有顶点且使每个顶点仅被访问一次，这一过程称为遍历图。
图的遍历比树的遍历复杂得多，由于图的任一顶点都可能和其余顶点相连接，因此在访问了某个顶点之后，可能顺着某条边又访问已被访问过的顶点。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组visited[]，用以标记顶点是否被访问过，其初态应为0（false）。一旦一个顶点vi被访问，则visited[i]=1（true）。
图遍历的基本方法有广度优先搜索和深度优先搜索。在实现这些算法时假设图以邻接表方式存储。
广度优先搜索（BFS）的基本思路是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1，vi2，……，vit，并均标记为已访问过，然后再按照vi1，vi2，……，vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。
例如，对于图6-8（a）的邻接表，从顶点0出发进行图广度优先搜索的过程是：
（1）先访问该顶点，并将初始顶点0插入到队列中。
（2）当队列不为空时进行第1轮循环。从队列中出队一个顶点，即顶点0，找到序号为0的表头节点，找到firstarc域指向的链表，该链表的第一个顶点是1，该顶点未访问过则访问它，并将其插入到队列中，在该链表中下移一个节点，即移到序号为3的顶点，该顶点未访问过则访问它，并将其插入到队列中。
（3）开始第2轮循环。从队列中出队一个顶点，即顶点1，找到序号为1的表头节点，找到firstarc域指向的链表，该链表的第一个顶点是0，该顶点已访问过则不访问它，在该链表中下移一个节点，即移到序号为2的顶点，该顶点未访问过则访问它，并将其插入到队列中。
（4）开始第3轮循环。从队列中出队一个顶点，即顶点3，找到序号为3的表头节点，找到firstarc域指向的链表，该链表的第一个顶点是1，该顶点已访问过则不访问它，在该链表中下移一个节点，即移到序号为3的顶点，该顶点已访问过则不访问它，在该链表中下移一个节点，即移到序号为4的顶点，该顶点未访问过则访问它，并将其插入到队列中。
（5）开始第4轮循环。从队列中出队一个顶点，即顶点2，找到序号为2的表头节点，找到firstarc域指向的链表，其中所有顶点均已访问。
（6）开始第5轮循环。从队列中出队一个顶点，即顶点4，找到序号为4的表头节点，找到firstarc域指向的链表，其中所有顶点均已访问。
（7）这时队列已空，退出循环，整个算法结束。所以最终的遍历序列是0，1，3，2，4。
实现广度优先搜索的非递归算法如下：
void BFS(AdjList *G,int vi) /*对邻接表G从顶点vi开始进行广度优先遍历*/
{
int i,v,visited[MAXVEX];
int Qu[MAXVEX],front=0,rear=0; /*循环队列*/
ArcNode *p;
for(i=0;i<G->n;i++) /*给visited数组置初值0*/
visited[i]=0;
printf("%d ",vi); /*访问初始顶点*/
visited[vi]=1; /*置已访问标识*/
rear=(rear=1)%MAXVEX; /*循环移动队尾指针*/
Qu[rear]=vi; /*初始顶点进队*/
while(front!=rear) /*队列不为空时循环*/
{
front=(front+1) % MAXVEX;
v=Qu[front]; /*顶点v出队*/
p=G->adjlist[v].firstarc; /*找v的第一个邻接点*/
while(p!=NULL) /*找v的所有邻接点*/
{
if (visited[p->adjvex]==0) /*未访问过则访问之*/
{
visited[p->adjvex]=1; /*置已访问标识*/
printf("%d ",p->adjvex); /*访问该点并使之入队列*/
rear=(rear+1) % MAXVEX; /*循环移动队尾指针*/
Qu[rear]=p->adjvex; /*顶点p->adjvex进队*/
}
p=p->next; /*找v的下一个邻接点*/
}
}
}
在上述算法设计好后，编写如下主程序调用这些函数：
void main()
{
int i,j;
AdjMatix g;
AdjList *G;
int a[5][5]={{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}};
char *vname[MAXVEX]={"a","b","c","d","e"};
g.n=5;g.e=12; /*建立图6-1(a)的无向图，每1条无向边算为2条有向边*/
for(i=0;i<g.n;i++)
strcpy(g.vexs[i].data,vname[i]);
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=a[i][j];
MatToList(g,G);
DispAdjList(G); /*输出邻接表*/
printf("从顶点0的广度优先遍历序列:\n");
printf("\t");BFS(G,0);printf("\n");
}
本程序的执行结果如下：
图的邻接表表示如下：
[0, a]=>(1,1)->(3,1)->∧
[1, b]=>(0,1)->(2,1)->∧
[2, c]=>(1,1)->(3,1)->(4,1)->∧
[3, d]=>(0,1)->(2,1)->(4,1)->∧
[4, e]=>(2,1)->(3,1)->∧
从顶点0的广度优先遍历序列:
0 1 3 2 4
深度优先搜索的基本思路是：从图G中某个顶点vi出发，访问vi，然后选择一个与vi相邻且没被访问过的顶点v访问，再从v出发选择一个与v相邻且未被访问的顶点vj访问，依此继续。如果当前已访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点w，从w出发按同样方法向前遍历。直到图中所有顶点都被访问。
例如，对于图6-8（a）的邻接表（对应图6-1（a）），从顶点0出发进行图深度优先搜索的过程是：
（1）找到序号为0的表头，访问，找其firstarc域指向的链表。
（2）该链表的第一个顶点是1，该顶点未访问过则访问它；指针移到序号为1的表头，找其firstarc域指向的链表。
（3）该链表的第一个顶点是0，该顶点已访问过则不访问它，再在该链表中下移一个节点，即移到序号为2的顶点，该顶点未访问过则访问它；指针移到序号为2的表头，找其firstarc域指向的链表。
（4）该链表的第一个顶点是1，该顶点已访问过则不访问它；再在该链表中下移一个节点，即移到序号为3的顶点，该顶点未访问过则访问它；指针移到序号为3的表头，找其firstarc域指向的链表。
（5）该链表的第一个顶点是0，该顶点已访问过则不访问它；再在该链表中下移一个节点，即移到序号为2的顶点，该顶点访问过则不访问它，再在该链表中下移一个节点，即移到序号为4的顶点，该顶点未访问过则访问它；指针移到序号为4的表头，找其firstarc域指向的链表。
（6）该链表的第一个顶点是2，该顶点访问过则不访问它，再在该链表中下移一个节点，即移到序号为3的顶点，该顶点访问过则不访问它，再在该链表中下移一个节点，这时next域为NULL。
（7）回退出上一个位置，序号为3的链表的所有邻接均访问完毕；回退出上一个位置，指针移到序号为2的单链表的下一个节点，即序号为4的节点，该顶点已访问则不访问它；回退出上一个位置，序号为1的链表的所有邻接均访问完毕；回退出上一个位置，指针移到序号为0的单链表的下一个节点，即序号为3的节点，该顶点已访问则不访问它。整个算法结束。所以最终的遍历序列是0，1，2，3，4。
实现深度优先搜索的递归算法如下：
int visited[MAXVEX];
void DFS(AdjList *g,int vi) /*对邻接表G从顶点vi开始进行深度优先遍历*/
{
ArcNode *p;
printf("%d ",vi); /*访问vi顶点*/
visited[vi]=1; /*置已访问标识*/
p=g->adjlist[vi].firstarc; /*找vi的第一个邻接点*/
while(p!=NULL) /*找vi的所有邻接点*/
{
if(visited[p->adjvex]==0)
DFS(g,p->adjvex); /*从vi未访问过的邻接点出发深度优先搜索*/
p=p->next; /*找vi的下一个邻接点*/
}
}
实现深度优先搜索的非递归算法如下：
void DFS1(AdjList *G,int vi) /*非递归深度优先遍历算法*/
{
ArcNode *p;
ArcNode *St[MAXVEX];
int top=-1,v;
printf("%d ",vi); /*访问vi顶点*/
visited[vi]=1; /*置已访问标识*/
top++; /*将初始顶点vi的firstarc指针进栈*/
St[top]=G->adjlist[vi].firstarc;
while(top>-1) /*栈不空循环*/
{
p=St[top];top--; /*出栈一个顶点为当前顶点*/
while(p!=NULL) /*循环搜索其相邻顶点*/
{
v=p->adjvex; /*取相邻顶点的编号*/
if(visited[v]==0) /*若该顶点未访问过*/
{
printf("%d ",v); /*访问v顶点*/
visited[v]=1; /*置访问标识*/
top++; /*将该顶点的第1个相邻顶点进栈*/
St[top]=G->adjlist[v].firstarc;
break; /*退出当前顶点的搜索*/
}
p=p->next; /*找下一个相邻顶点*/
}
}
}
在上述算法设计好后，编写如下主程序调用这些函数：
void main()
{
int i,j;
AdjMatix g;
AdjList *G;
int a[5][5]={{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1, 1,0}};
char *vname[MAXVEX]={"a","b","c","d","e"};
g.n=5;g.e=12; /*建立图6-1(a)的无向图，每1条无向边算为2条有向边*/
for(i=0;i<g.n;i++)
strcpy(g.vexs[i].data,vname[i]);
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=a[i][j];
MatToList(g,G);
DispAdjList(G); /*输出邻接表*/
for(i=0;i<g.n;i++) visited[i]=0; /*顶点标识置初值*/
printf("从顶点0的深度优先遍历序列:\n");
printf("递归算法:");DFS(G,0);printf("\n");
for(i=0;i<g.n;i++) visited[i]=0; /*顶点标识置初值*/
printf("非递归算法:");DFS1(G,0);printf("\n");
}
本程序的执行结果如下：
[0, a]=>(1,1)->(3,1)->∧
[1, b]=>(0,1)->(2,1)->∧
[2, c]=>(1,1)->(3,1)->(4,1)->∧
[3, d]=>(0,1)->(2,1)->(4,1)->∧
[4, e]=>(2,1)->(3,1)->∧
从顶点0的深度优先遍历序列:
递归算法:0 1 2 3 4
非递归算法:0 1 2 3 4