应用题 6.已有邻接表表示的有向图,请编程判断从第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 f=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(tt%3d\n”,v):
}//if
else{visited[i]=1;s[++top]=i;} //else深度优先遍历
}//else
}//while
}
【答案解析】