试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。
试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。
正确答案:int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level=1;//递归进行的层数 int exist()path()DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc,level--) { level++; k=p->adjvex; if(!visited[k]&;&;exist()path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level==1) return 0; }//exist()path()DFS