软考在线  |  计算机技术与软件专业技术资格(水平)考试   |   [请选择科目]
[ 成为 VIP会员 ]        登录  |  注册      我的  购物车
 
科目切换  联系我们 
    
  |   [请选择科目]

VIP:有效提升20分!  真题  历年真题 (可免费开通)/  百科全书/ 机考模拟平台/  最难真题榜/  自测/  攻打黄金十二宫/  真题检索/  真题下载/  真题词库
知识   必会知识榜/  最难知识榜/  知识点查询/      文档   学习计划/  精华笔记/  试题文档     纸质图书   《百科全书》HOT!!/         /        首页/  2025年上半年专区/  手机版/ 
免费智能真题库 > 历年试卷 > 系统分析师 > 2022年上半年 系统分析师 上午试卷 综合知识
  第56题      
  知识点:   最小生成树
  章/节:   图论应用       

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

 
 
  A.  A
 
  B.  C
 
  C.  D
 
  D.  E
 
 
 确定 并 查看答案解析     知识点讲解  我要标记      有奖找茬      上一题        下一题 
 

 
  第2题    2024年下半年  
   0%
开发商需要在某小区9栋楼房之间敷设自来水管道,使各楼都能连通,又能使总成本最低。经勘察,各楼房之间敷设管道的路径和成本(单..
  第57题    2011年上半年  
   52%
已知某山区六个乡镇C1,C2,…,C6之间的公路距离(公里数)如下表:

其中符号“表示两个乡镇之间没有直通公..
  第5题    2024年下半年  
   0%
已知某山区六个乡镇C1,C2,…,C6之间的公路距离(公里数)如下表:

其中符号“表示两个乡镇之间没有直通公..
   知识点讲解    
   · 最小生成树
 
       最小生成树
        一个连通且无回路的无向图称为树。在树中度数为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题    在手机中做本题
    在线人数   共计 15328人 在线 
    lc811002@1..     liang.1007..     kairos_lea..     451572485@..     moucu1@yah..     fzmzf@163...
    yujianhua-..     liang.1007..     hanqingwei..     zhang_shua..     wds@dc-pol..     miao2001on..
    hyy49@126...     lxf@fyqyjt..     rnchen_200..     erinlcy@ya..     hongyongqi..     ygzgz74309..
    menyan3222..     630901590@..     wugangroom..     805023188@..     mayue_1206..     hy_cuicui@..
    koujia2000..     heweiping2..     xuxiaolong..     xushanxian..     yyping0116..     wisoon@yah..
    351246118@..     837850688@..     chenwangen..     zhangfeng8..     jiaruihz@v..     86501591@1..
    xch808@163..     shengzeng@..     yk94609@12..     xiao.mo.ok..     huoyanfeng..     xch808@163..