首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
admin
2012-06-21
88
问题
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问:
(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
学硕统考专业
相关试题推荐
1933年美国通过的《工业复兴法》规定:“雇主不得工人参加何种工会为雇佣条件;必须遵守工时……工资限额。”这一法令说明()
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为封建社会
以下古代文件起到了限制王权作用的是()。
第一国际成立于下面的哪个城市?()
李大钊是在中国传播马克思主义最早的革命先驱者,下列李大钊的著作中,不属于揭开了我国马克思主义宣传的第一页的是()。
关于大陆人民大规模达到台湾的第一次明确的记录出现在()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
简述苏联高度集中的经济政治体制的主要特征。
请根据下面材料,结合相关知识,分析其内容及意义。他命令所有罗马人都进行登记并用银对自己的财产估价,按照习惯宣誓保证所报各项均属真实,全部财产均已按最高价格估价,并陈报父亲系何人,自己的年龄,自己的妻子和子女的名字,每人的籍贯隶属市中哪个部落或乡间
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
随机试题
反映对可持续发展有影响的指标是()
茕茕子立,形影相吊出自( )
预防小儿结核病的有效措施是
下列属于反式作用因子的是()
营业税属于以下税种中的()。
某总承包单位与分包单位在分包合同中约定,由分包单位自行负责分包工程的安全生产。工程施工中,分包工程发生了安全事故,则该事故()。
某工程公司与劳动者齐某双方发生劳动争议后,经过平等协商,双方达成了一个和解协议,那么对该和解协议理解正确的是()。
进口传感器在向海关申报时,应使用下列何种报关单()。报关员报关行为不规范而被海关记5分的情形有()。
Therearemanybooksontheshelf,someareEnglish,______areChinese.
InanuncriticalAugust11,1997,WorldNewsTonightreporton"diamagnetictherapy,"aphysicaltherapistexplainedthat"magne
最新回复
(
0
)