首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
admin
2012-06-21
115
问题
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问:
(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
学硕统考专业
相关试题推荐
在大革命失败后,毛泽东对开辟中国革命新道路的主要贡献。
毛泽东在《关于正确处理人民内部矛盾的问题》中指出,社会主义社会的基本矛盾是()。
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
规定了电流、电动势、电阻等概念的物理学家是()。
概括指出新民主主义革命各个阶段中国社会的主要矛盾及其表现形式的演变,说明中共根据上述变化对政策的调整及其结果。
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
中古时代实行索贡巡行赋税征收方式的国家是()。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为带书。④马钧发明翻车
在新民主主义革命中,工人阶级、农民阶级和城市小资产阶级的政治代表是()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发
随机试题
以反应迅速、有朝气、活泼好动、动作敏捷为特征的气质类型是()
有关菌状乳头的特征的描述,错误的是()
出现杜加(Dugas)征的疾病是
下列胁痛的病机哪一项是错误的
某患者无青霉素过敏史,青霉素皮试阴性,护士随即遵照医嘱给药,几分钟后患者突然发生休克,这种状况应判定为()
“重罪十条”首载于_________。
案例:学习目标:(1)增强奔跑能力,发展心肺功能。(2)提高自主学练能力。(3)培养探究精神,提高合作学习的能力。学习内容:跑动性游戏。学习步骤:(1)教师给学生们三个排球,让学生自主创
管理的二重性是指管理的()。
Sometimesthemessagesareconveyedthroughdeliberate,consciousgestures;othertimes,ourbodiestalkwithoutourevenknowin
主体和客体作为实践和认识的两个基本要素,它们的关系是()。
最新回复
(
0
)