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

admin2019-08-15  26

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

选项

答案 void Allpath(AdjList g,vertype u,vertype v){ //求有向图g中顶点u到顶点v的所有简单路径,初始调用形式 int top=0,S[]: S[++top]=u;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=l;k<=top;k++)printf("%3d",s[k]); printf(”%3d\n",v); }//if else{visited[i]=l;s[++top]=i;} //else深度优先遍历 }//else }//while }

解析
转载请注明原文地址:https://jikaoti.com/ti/QsGjFFFM
0

相关试题推荐
最新回复(0)