已有邻接表表示的有向图,请编程判断从第u顶点至第v顶点是否有简单路径,若有则打印出该路径上的顶点。

admin2019-08-01  20

问题 已有邻接表表示的有向图,请编程判断从第u顶点至第v顶点是否有简单路径,若有则打印出该路径上的顶点。

选项

答案void Allpath(AdjList g,vertype u,vertype v){ //求有向图g中顶点u到顶点v的所有简单路径,初始调用形式 int top=0,S[]; S[++top]=ui visited[u]=1; while(top>0 || P){ p=g[S[top]].firstarc; //第一个邻接点 while(P!=null && visited[p一>adjvex]==1)P=p->next;//下一个访问邻接点表 if(P==null)top一一; //退栈 else{ i=p->adjvex; //取邻接点(编号) if(i==v){ //找到从U到v的一条简单路径,输出 for(k=1;k<=top;k++)printf(”%3d”,s[k]); printf(”%3d\n”,v); }//if else{visited[i]=1;s[++top]=i;} //else深度优先遍历 }//else }//while }

解析
转载请注明原文地址:https://kaotiyun.com/show/sVCi777K
0

最新回复(0)