首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
admin
2012-06-21
89
问题
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问:
(1)可用什么数据结构来表示城镇和道路;
(2)请用伪代码描述效率最高的解法。
选项
答案
(1)用图结构表示,其中顶点表示城镇,顶点之间路径表示道路。 (2)这个应该是特殊(道路权重为1)的prim算法。 采用邻接表结构,顶点结构包括:known表示时候已经加入,dist表示到起点的道路条数,path表示相连的城镇。算法如下: void unweight(Table T) { Queue Q; Vertex v,w; Q=CreateQueue(NumVertex);MakeEmpty(Q); Enqueue(S,Q);//s表示起点,可为任一城镇。 While(!IsEmpty(Q)) { V=Dequeue(Q); T[V].Known=True; For each w adajcent to v If(T[w].Dist==Infinity) { T[w].dist=T[v].dist+1;T[w].path=v;Enqueue(w,Q)) } DisposeQueue(Q); } dfstravrese(G.visit(int v)) { boolean Visited[MAX]; initstack(S); for(v=0;v<=G.maxvexnum;v++)Visited[v]=FLASE; for(v=0;v<=G.maxvexnum;v++) if(Visited[v]==FLASE) { push(s,v); DFS(G,v); } while(!Stackempty(S)) { printf("%d",v); } } DFS(G,w) { Visited[w]=TRUE; for(firstadjvex(G,w);w>=0;w=nextadjvex(G,w)) { Visited[w]=TRUE; ; } }
解析
转载请注明原文地址:https://kaotiyun.com/show/QAxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
确定我国经济体制改革目标的核心问题是正确认识和处理()。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
氏族公社形成的条件和基本标志是()。
不仅主张通过三种国家权力的分立达到相互制衡的目的,而且提出通过国家与地方政府的分权更好地实施对权力的制约的思想家是()。
西欧早期资产阶级反封建斗争以反天主教会的方式进行,主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起
()是清代管理边疆少数民族地区事务的机关,也掌管一部分外交事务。
关于荷马时代的叙述,不正确的是()。
《齐民要求.序》中写道:“今采摭经传,爰及歌谣,洵之老成,验之行事,起自农耕,终于醯醢(酱醋),资生之靡不毕书书;号日《齐民要术》……舍本逐末,贤哲所非……故商贾之事,阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
阅读以下史料,并回答问题:初,范阳祖逖,少有大志,与刘琨俱为司州主簿,同寝,中夜闻鸡鸣,蹴琨觉,曰:“此非恶声也!”因起舞。及渡江,左丞相睿以为军谘祭酒。逖居京口,纠合骁健,言于睿曰:“晋室之乱,非上无道而下怨叛也,由宗室争权,自相鱼肉,遂使戎狄乘隙,毒
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
随机试题
七件圣事,又称七件圣礼,这是天主教、东正教的重要礼仪。新教主张取消一些繁琐的礼仪,主张只保留()。
对企业日常发生的各项基本活动的预算是()
制定药品管理法的目的不包括
男,41岁。胃部不适、食欲减退3个月。胃镜检查发现胃窦前壁直径0.5cm的浅溃疡,幽门螺杆菌阳性。超声胃镜示病变侵及浅肌层,病理可见印戒细胞。最适当的治疗是()
关于乳房,下列说法错误的是()。
【真题(中级)】按照预算期的时间特征不同分类,经营预算编制的方法有()。
在一手个人住房交易时,在借款人购买的房屋没有办好抵押登记之前,由()提供阶段性或全程担保。
在中国历史上,将“巡捕”和“巡警”改为警察的是()。
在C++中,函数原型不能标识______。
LanguageVarietiesLanguagesconstantlyundergochanges,resultinginthedevelopmentofdifferentvarietiesofthelanguage
最新回复
(
0
)