【正确答案】算法1：
int visited[ ]=0; //全局变量，访问数组初始化
int dfs(AdjList g, vi){
//以邻接表存储的有向图g，判断vi到vj是否有通路，返回1或0
visited[vi] = 1; //visited是访问数组，设顶点的信息就是顶点编号
p = g[vi].firstarc; //第一个邻接点
while(p != null){
j = p-＞adjvex;
if(vj == j){ flag = 1; return(1); } //vi和vj有通路
if(visited[j]==0 )dfs(g,j);
p=p-＞next;
}//while
if(! flag) return(0);
算法2：输出vi到vj的路径，其思想是用一个栈存放遍历的顶点，遇到顶点vj时输出路径。
void dfs(AdjList g, int i){ //顶点vi和顶点vj间是否有路径，如有，则输出
int top = 0, stack[]; //stack是存放顶点编号的栈
visited[i]=1; //visited数组在进入dfs前已初始化
stack[++top]=i;
p=g[i].firstarc; //求第一个邻接点
while(p){
if(p-＞adjvex==j){
stack[++top] = j;
printf("顶点vi和vj的路径为:/n");
for(i=1; i＜=top; i++) printf("%4d", stack[i]);
exit(0);
}
else if(visited[p-＞adjvex]==0){ dfs(g,g-＞adjvex); top--; p=p-＞next; }
}
}
算法3：非递归算法求解。
int Judge(AdjList g, int i, j){
//判断n个顶点以邻接表示的有向图g中，顶点vi各vj是否有路径，
//有则返回1，否则返回0。
for(i=1; i＜=n; i++)visited[i]=0; //访问标记数组初始化
int stack[], top=0; stack[++top]=vi;
while(top＞0){
k=stack[top--]; p = g[k].firstarc;
while(p !=null && visited[p-＞adjvex]==1) p=p-＞next;
//查第k个链表中第一个未访问的弧结点
if(p==null) top--;
else{
i = p-＞adjvex;
if(i==j) return(1); //顶点vi和vj间有路径
else{ visited[i]=1; stack[++top]=i; }
}
}while
return(0);
}//顶点vi和vj间无通路
【答案解析】此题考查的知识点是图的遍历。在有向图中，判断顶点vi和顶点vj间是否有路径，可采用搜索的方法，从顶点vi出发，不论是深度优先搜索(DFS)还是宽度优先搜索(BFS)，在未退出DFS函数或BFS函数前，若访问到vj，则说明有通路，否则无通路。设一全程变量flag，初始化为0，若有通路，则flag=1。