首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问: (1)
admin
2012-06-21
110
问题
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路即可),并要求增设的道路条数为最少,要解决这个问题,问:
(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
学硕统考专业
相关试题推荐
巴黎和会讨论的中心问题是()。
氏族公社形成的条件和基本标志是()。
在英国革命中,平等派的领导人是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
关于俄国工业革命的特点,正确的是()。①外国资本和技术在工业革命中起着重要的作用②工业革命发展极不平衡③企业资本有机构成低,技术落后④工业革命所需的资金主要来自对海外殖民地的掠夺
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发
最早以立法形式巩固大化改新成果的法令是()。
晚清时期清帝年号的正确排序是()
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
随机试题
在系统说明书的内容中,资源预算属于__________。
牙震荡伤有轻微叩痛和松动,必要时可采用
咽部一侧或咽后壁明显红肿高突,吞咽困难,身发寒热者,为咽部一侧或两侧喉核红肿疼痛,溃烂有黄白色脓点,脓汁拭之易去者,为
男,20岁。咳嗽半年,偶有咯血,乏力、体重下降明显,体温正常。查体:双侧颈淋巴结蚕豆样大小,质稍硬,无触痛;右上肺可闻及少量湿啰音。该患者最可能的诊断为
依据《安全生产检测检验机构管理规定》,检测检验机构应当在每年()月份向资质证书颁发机关报送上一年度的工作总结和本年度的工作计划。
在()发现的原始人的打制石器是目前河北省境内发现的最早的人类遗物。
材料:以下是关于“日本的自然环境特征”的教学过程设计。(1)导入:播放有关富士山、樱花、东京景色、和服、寿司的图片,引出课堂主题——衣、食、住、行聊日本。(2)学生学习成果展示:事先安排学生分成四个小组分别研究日本的衣、食、住、行,在
通货膨胀:钱不值钱了()
从中华人民共和国成立到社会主义改造基本完成,是我国从新民主主义到社会主义过渡的时期。这一时期,我国社会的性质是新民主主义社会。在新民主主义社会中,有五种经济成分,其中主要的经济成分是()
CardinalMezzofantiofBolognawasasecularsaint.Thoughheneverperformedthekindofmiracleneededtobeofficiallycanoni
最新回复
(
0
)