首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2017-11-14
34
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点V
i
到顶点V
j
的路径(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://kaotiyun.com/show/yDRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述苏联解体的原因。
关于斯巴达的论述错误的是()。
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
下列有关西欧封建社会的表述,错误的一项是()。
对西欧封建社会的说法不正确的是()。
美国首次提出争夺世界霸权的纲领性文件是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争,这一古老文件是()。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
通过对方格中每个点设置相应的CMYK值就可以将方格涂上相应的颜色。以下3个程序段都可实现对一个8×8的方格涂上黄色的功能。假设Cache的数据区大小为512B,采用直接映射,块大小为32B,存储器按字节编址,sizeof(int)=4
随机试题
一个时期某一阶层或某一行业的人群对文化问题所持的态度和看法,或在某一文化事象里所表现的意识形态,称作______。
A、2岁以下B、青壮年C、成年D、老年男性E、3~10岁儿童小肠套叠常见于
以下哪一种植物不属于川贝母的原植物
某项目现金流量表(单位:万元)如下:则该项目的净现值和动态投资回收期分别为()。
在进行预算定额人工工日消耗量计算时,完成单位合格产品的基本用工为22工日,超运距用工为4工日,辅助用工为2工日,人工幅度差系数为12%,则预算定额中人工工日消耗量为()工日。
某旅馆建筑高度为24m,设有空气调节系统、无楼层服务员以及客房、餐厅、仓库、办公室等功能用房,无高位水箱,但设有临时高压给水,3L/s的气压稳压设备,并设湿式自动喷水系统,且仅在走道上安装黄色玻璃球喷头。请结合案例。分析并回答以下问题:该旅馆的自动喷水
行政程序的主要制度包括()。
如果菜单项的名称为“统计”,热键是T,在菜单名称一栏中应输入
Besidesa_______knowledgeofbusinessadministration,candidatesmusthaveaminimumof2years’experienceforthisproject.
Theeconomystoppedshrinkingayearago,butAmerica’sunemploymentproblemisasbigasever.Theofficialjoblessratewas9.
最新回复
(
0
)