2. 考研
  3. 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问： (1)

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问： (1)

admin2012-06-21  77
问题 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：
  (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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)