免费智能真题库 > 历年试卷 > 系统分析师 > 2022年上半年 系统分析师 上午试卷 综合知识
  第56题      
  知识点:   最小生成树
  章/节:   图论应用       

 
某乡有7个小山村A~G,村与村之间原有小路可加宽修建公路的线路如下图所示(路边的数字表示路长的公里数)。为实现村村通公路,修建公路总长至少(55)公里。若在(56)村新建一所中学,则可以使人们从离它最远的村到该校所走的优化路程最短。

 
 
  A.  A
 
  B.  C
 
  C.  D
 
  D.  E
 
 
 

 
  第58题    2017年上半年  
   62%
已知八口海上油井(编号从1#到8#) 相互之间的距离(单位:海里)如下表所示,其中1#油井离海岸最近为5海里。现从海岸开始铺设输油管..
  第57题    2011年上半年  
   52%
已知某山区六个乡镇C1,C2,…,C6之间的公路距离(公里数)如下表:

其中符号“表示两个乡镇之间没有直通公..
  第55题    2020年下半年  
   53%
某乡8个小村(编号为1?8)之间的距离如下表(单位:km)。1号村离水库最近,为5km,从水库开始铺设水管将各村连接起来,最少需要铺设..
   知识点讲解    
   · 最小生成树
 
       最小生成树
        一个连通且无回路的无向图称为树。在树中度数为1的节点称为树叶,度数大于1的节点称为分枝点或内节点。
        给定图T,以下关于树的定义是等价的:
        (1)无回路的连通图。
        (2)无回路且e=v-1,其中e为边数,v为节点数。
        (3)连通且e=v-1。
        (4)无回路且增加一条新边,得到一个且仅一个回路。
        (5)连通且删去任何一个边后不连通。
        (6)每一对节点之间有一条且仅一条路。
        在带权的图G的所有生成树中,树权最小的那棵生成树,称作最小生成树。
        求连通的带权无向图的最小生成树的算法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
               普里姆算法
               设已知G=(VE)是一个带权连通无向图,顶点V={0,1,2,…,n-1}。设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时,U只包含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合,初始时T为空。如果边(ij)具有最小代价,且iUjV-U,那么最小生成树应包含边(ij)。把j加到U中,把(ij)加到T中。重复上述过程,直到U等于V为止。这时,T即为要求的最小生成树的边的集合。
               普里姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小,因此这是一种贪心的策略。普里姆算法的时间复杂度为On2),与图中边数无关,所以适合于稠密图。
               克鲁斯卡尔算法
               设T的初始状态只有n个顶点而无边的森林T=(Vφ),按边长递增的顺序选择E中的n-1条安全边(uv)并加入T,生成最小生成树。所谓安全边是指两个端点分别是森林T里两棵树中的顶点的边。加入安全边,可将森林中的两棵树连接成一棵更大的树,因为每一次添加到T中的边均是当前权值最小的安全边,MST性质也能保证最终的T是一棵最小生成树。
               克鲁斯卡尔算法的特点是当前形成的集合T除最后的结果外,始终是一个森林。克鲁斯卡尔算法的时间复杂度为Oelog2e),与图中顶点数无关,所以较适合于稀疏图。
               
               求图的最小生成树
               例如,使用普里姆算法构造上图的最小生成树的过程如下5个图所示。
               
               使用普里姆算法构造最小生成树的过程(1)
               
               使用普里姆算法构造最小生成树的过程(2)
               
               使用普里姆算法构造最小生成树的过程(3)
               
               使用普里姆算法构造最小生成树的过程(4)
               
               使用普里姆算法构造最小生成树的过程(5)
   题号导航      2022年上半年 系统分析师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第56题    在手机中做本题