首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-08-15
27
问题
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点V
i
到顶点V
j
的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
选项
答案
算法1: int visited[]=0; //全局变量,访问数组初始化 int dis(AdjList g,vi){ //以邻接表存储的有向图g,判断vi到vj是否有通路,返回1或0 visited[vi]=l; //visited是访问数组,设顶点的信息就是顶点编号 P=g[vi].firstare; //第一个邻接点 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=l;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中,项点v
i
各v
j
是否有路径, //有则返回1,否则返回O。 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间无通路 提示:此题考查的知识点是图的遍历。在有向图中,判断顶点v
i
和顶点v
j
间是否有路径,可采用搜索的方法,从顶点v
i
出发,不论是深度优先搜索(DFS)还是宽度优先搜索(BFS),在未退出DFS函数或BFS函数前,若访问到v
j
,则说明有通路,否则无通路。设一全程变量flag,初始化为0,若有通路,则flag=1。
解析
转载请注明原文地址:https://kaotiyun.com/show/vdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
庆历新政是统治集团内部为了改革弊病而进行的一次努力。回答问题:范仲淹在()中提出了具体的改革方案。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
基督教产生的时间是()。
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述,不正确的是()
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
有效容量为128KB的Cache,每块16字节,8路组相联。字节地址为1234567H的单元调入该Cache,其Tag应是()。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
行政组织的物质要素包括()
男孩,15岁。打篮球后左膝关节肿胀疼痛就诊。检查:左膝关节局部肿胀,压痛明显,膝关节及其周围有大片瘀斑。其兄有血友病A病史。本例确诊为血友病A,下列哪项治疗是错误的
患者,男,54岁。右上肺癌,在住院化疗期间渐起右下肢肿胀疼痛,血管超声检查提示深静脉血栓,予抗凝治疗一度有所改善。早餐进食时突感胸闷、气紧、心前区疼痛,呈进行性加重。查体:明显发绀,不能平卧,心界扩大,心率110次/分,律齐,P2亢进,三尖瓣区闻及收缩期杂
糖尿病易合并肾功能不全是因为
行政拘留是最为严厉的治安处罚,其最长期限为不超过20日。( )
给定资料1.2017年12月29日晚,武汉华中科技大学教学楼五楼二中教室正在进行一场人文讲座,李教授关于“诗和远方”“历史唯物主义与浪漫主义"等人生意义的哲学思考不时引发学生们的热烈掌声。自1994年以来,这样的讲座已经在华中科技大学举行了220
根据有关基础资料和国民经济核算方法,2014年上半年我国GDP初步核算结果如下:2014年上半年,第二产业GDP约为第一产业GDP的()倍。
以下程序:#include#includemain(){charstr[]="abcd\123Lxab";printf("%d",strlen(str));}运行后的输出结果
InspectorMarshallwas______forhisprofessionalandcaringattitude.
A、Skateboarding.B、Rollerskating.C、Cycling.D、Surfing.A细节题。浏览选项可知,问题与运动有关。从对话一开始,男士就明确提到他户外的onlyrecreation(唯一的娱乐活动)是skateboa
最新回复
(
0
)