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

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

admin2019-01-16  53
问题 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点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]==O)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。
转载请注明原文地址:https://kaotiyun.com/show/9lRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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