给定一个图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