2. 考研
  3. 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)

试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)

admin2017-11-14  39
问题 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)
选项
答案算法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间是否有路径，如有，则输出 inllop=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，否则返回O。 for(i=1；i<=n；i++)visited[i]=0 i ／／访问标记数组初始化 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间无通路
解析
转载请注明原文地址:https://www.kaotiyun.com/show/yDRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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