7.3.3 图遍历算法的应用.pptx

7.3.3图遍历算法的应用;intConnect(AdjGraph*G) //判断无向图G的连通性

{inti,flag=1;

DFS(G,0); //调用DFS算法,从顶点0开始深度优先遍历

for(i=0;iG-n;i++)

if(visited[i]==0)

{flag=0;

break;

}

returnflag;

};【例7.9】假设图G采用邻接表存储，设计一个算法判断顶点u到顶点v之间是否有简单路径。;intvisited[MAXVEX]; //全局数组

intHasaPath(AdjGraph*G,intu,intv)

{ArcNode*p;

intw;

visited[u]=1;

p=G-adjlist[u].firstarc;//p指向u的第一个相邻点

while(p!=NULL)

{w=p-adjvex; //相邻点的编号为w

if(w==v) //找到顶点v后返回1

return1;

if(visited[w]==0) //若顶点w没有访问过

{if(HasaPath(G,w,v)) //从w出发进行深度优先遍历

return1; //若从w出发找到顶点v返回1

}

p=p-nextarc; //p指向下一个相邻点

}

return0; //没有找到顶点v，返回0

};从递归算法设计的角度求解本问题;【例7.10】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v之间的一条简单路径（假设两顶点之间存在一条或多条简单路径）。;voidFindaPath(AdjGraph*G,intu,intv,intpath[],intd)

{ArcNode*p;intw,i;

visited[u]=1;

d++;path[d]=u; //顶点u加入到路径中

if(u==v) //找到一条路径

{for(i=0;i=d;i++) //输出找到一条路径并返回

printf(%d,path[i]);

printf(\n);

return;

}

p=G-adjlist[u].firstarc; //p指向u的第一个相邻点

while(p!=NULL)

{w=p-adjvex; //相邻点的编号为w

if(visited[w]==0)

FindaPath(G,w,v,path,d); //递归调用

p=p-nextarc; //p指向下一个相邻点

}

};【例7.11】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v之间的所有简单路径（假设两顶点之间存在一条或多条简单路径）。;解：采用带回溯的DFS设计求解算法FindallPath(G，u，v，path，d)。

先置visited数组的所有元素值为0。

从顶点u开始，置visited[u]=1，将u放入path，若找到u的未访问过的相邻点u1，继续下去，若找不到u的未访问过的相邻点，置visited[u]=0以便u成为另一条路径上的顶点（这称为回溯）；再从顶点u1出发，置visited[u1]=1，将u1放入path，若找到u1的未访问过的相邻点u2，继续下去，若找不到u1的未访问过的相邻点，置visited[u1]=0以便u1成为另一条路径上的顶点（回溯），…。

当找到的某个未访问过的相邻点un=v，说明path中存放的是顶点u到v的一条简单路径，输出path。

每次输出的path构成顶点u到v的全部简单路径中的一条，所有输出的path构成顶点u到v的全部简单路径。;voidFindallPath(AdjGraph*G,intu,intv,intpath[],intd)

{ArcNode*p;intw,i;

visited[u]=1;

d++;path[d]=u; //顶点u加入到路径中

if(u==vd=1) //找到一条长度=1的简单路径

{for(i=0;i=d;i++) //输出找到一条路径并返回

printf(%d,path[i]);

printf(\n);

}

p=G-adjlist[u].firstarc; //p指向u的第一个