首页 > 试题广场 >

用(a,b,c)表示节点a,b之间有一条权值为c的无向边。对

[单选题]
用(a,b,c)表示节点a,b之间有一条权值为c的无向边。对于图(1,2,3),(1,3,4),(1,5,1),(2,3,4),(2,4,6),(2,5,2),(3,5,1)。最小生成树的权值和为(        ) 
  • 9
  • 10
  • 11
  • 12
查看答案及解析
添加回答
天尊墨宇头像 天尊墨宇
 选B
  • 选择 1 号节点作为初始子图 MST = (node, edge)；
  • 对外连接的边分别是：(1,5,1), (1,2,3), (1,3,4)，最小边是(1,5,1)；
  • 则将 5 号节点纳入当前子图，node = {1, 5}；
  • 对外连接的边分别是：(5,3,1), (5,2,2), (1,2,3), (1,3,4)，最小边是(5,3,1)；
  • 则将 3 号节点纳入当前子图，node = {1, 3, 5}；
  • . . . . . .(如此重复直到包含了所有节点) . . . . . .
    • 发表于 2020-07-12 09:24:01 回复(0)
    凉风起天末头像 凉风起天末
    一、将图还原（如上图）
    二、选择算法生成最小生成树（Prim是节点驱动的，而Kruskal是边驱动的），以Prim算法为例：
    1. 任意选择一个起点作为初始子图，放入 MST.node 中（MST : Minimum Spanning Tree）；
    2. 从当前子图所有对外连接的边中选择权最小的一条E（“对外连接” 指的是：边的一端在当前子图内，而另一端不在当前子图内）；
    3. 将E和对应的外部节点N纳入当前子图 MST 中，子图生长；
    4. 重复第2步，直到 MST 包含了原图的所有节点；
    三、Prim算法过程演示：
    1. 选择 1 号节点作为初始子图 MST = (node, edge)；
    2. 对外连接的边分别是：(1,5,1), (1,2,3), (1,3,4)，最小边是(1,5,1)；
    3. 则将 5 号节点纳入当前子图，node = {1, 5}；
    4. 对外连接的边分别是：(5,3,1), (5,2,2), (1,2,3), (1,3,4)，最小边是(5,3,1)；
    5. 则将 3 号节点纳入当前子图，node = {1, 3, 5}；
    6. . . . . . .(如此重复直到包含了所有节点) . . . . . .
    发表于 2019-09-19 11:12:36 回复(0)
    0_0?头像 0_0?
    • 如下图所示：黑色结点代表已选结点，黑色实线代表已选无向边，灰色结点代表未选结点，灰色虚线代表待选无向边；
    • 首先选择结点①作为最小生成树的开始结点，在与结点①相连的三条边中，结点①与结点⑤相连的无向边权值最小，将结点⑤纳入最小生成树；
    • 在与当前树相连的四条边中，权值最小的是结点⑤与结点③相连的无向边，将结点③纳入最小生成树；
    • 在与当前树相连的三条边中，权值最小的是结点⑤与结点②相连的无向边，将结点②纳入最小生成树；
    • 与当前树相连的边只有一条，即结点②与结点④相连的无向边，将结点④纳入最小生成树；
    • 所以最小生成树的权值和=1+1+2+6=10。

    发表于 2021-10-26 15:32:42 回复(0)
    已注销头像 已注销
    克鲁斯卡尔~
    发表于 2022-03-05 21:31:56 回复(0)
    西暮头像 西暮
    啊 无向图啊😀真棒
    发表于 2020-05-24 21:53:36 回复(0)
    提交观点

    问题信息

    测试开发工程师 测试工程师 图 2018 360集团
    来自：360公司-2018春...
    上传者：小小
    难度：
    5条回答 3219浏览

    热门推荐

    相关试题

    扫一扫，把题目装进口袋

    求职之前，先上牛客

    扫描二维码，进入QQ群

    扫描二维码，关注牛客公众号