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

admin2019-08-01  29

问题 已有邻接表表示的有向图,请编程判断从第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=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/8NCi777K
0

最新回复(0)