已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

题目

已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

相似考题

1.设V'和E'分别为无向连通图G的点割集和边割集，下面的说法中正确的是Ⅰ．G-E'的连通分支数p(G-E')=2。Ⅱ．G-V'的连通分支数p(G-V')一定等于G-E'的连通分支数p(G-E')。Ⅲ．G-V'的连通分支数p(G-V')≥2。A．Ⅰ和ⅡB．Ⅰ和ⅢC．ⅡD．没有

2.应用题:已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。

3.在有向图的邻接表表示中,顶点v在边单链表中出现的次数是()。A.顶点v的度B.顶点v的出度C.顶点v的入度D.依附于顶点v的边数

4.已知一个图的顶点集V={1,2,3,4,5,6,7};边集E={()3,()5,()8,()10,()6,()15,()12,()9,()4,()20,()18,()25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为()。A、(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20B、(1,2)3,(4,6)4,(1,3)5,(2,3)6,(1,4)8,(3,6)9C、(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20D、(1,2)3,(1,3)5,(1,4)8,(2,5)10,(4,6)4,(4,7)20

更多“已知一个图的顶点集V和边集E分别为:V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3) ”相关问题

  • 第1题：

    在有向图的邻接表表示中,顶点v的边单链表中的结点个数等于()。

    A.顶点v的度

    B.顶点v的出度

    C.顶点v的入度

    D.依附于顶点v的边数


    参考答案：B

  • 第2题：

    有以下程序：程序运行后的输出结果是（ ）.

    A.1，3

    B.2，3

    C.1，4

    D.1，2


    正确答案：A
    在f(int*P，int*q)函数中，执行P=P+1将P所对应的地址加1，而*q=*q+1是将q所指向的n的地址所对应的值加1，即m的地址所对应的值不变。而n的值为3。

  • 第3题：

    已知如图所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。

    AV1V2V4V8V5V3V6V7

    BV1V2V4V5V8V3V6V7

    CV1V2V4V8V3V5V6V7

    DV1V3V6V7V2V4V5V8


    A
    略

  • 第4题：

    在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）


    正确答案:正确

  • 第5题：

    若一个图的顶点集为{a，b，c，d，e，f}，边集为{（a，b），（a，c），（b，c），（d，e）}，则该图含有（）个连通分量。


    正确答案:3

  • 第6题：

    假定一个有向图的顶点集为{a，b，c，d，e，f}，边集为{， ， < c，f>， < d，c>， < e，b>， < e，d>}，则出度为0的顶点个数为（），入度为1的顶点个数为（）


    正确答案:2；4

  • 第7题：

    某系统包含3个单元 ，其最小割集为{1，2}、{1，3}和{2，3}，则该系统为（）模型。

    • A、串联
    • B、表决
    • C、旁联
    • D、桥联

    正确答案:B

  • 第8题：

    单选题
    固定资产“搭桥”贷款期限一般不超过（）年，最长不超过（）年。
    A

    1，2

    B

    1，3

    C

    2，3

    D

    2，5


    正确答案： C
    解析： 暂无解析

  • 第9题：

    单选题
    用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（）组中选取。
    A

    {（1，4），（3，4），（3，5），（2，5）}

    B

    {（5，4），（5，3），（5，6）}

    C

    {（1，2），（2，3），（3，5）}

    D

    {（3，4），（3，5），（4，5），（1，4）}


    正确答案： B
    解析： 暂无解析

  • 第10题：

    单选题
    某系统包含3个单元 ，其最小割集为{1，2}、{1，3}和{2，3}，则该系统为（）模型。
    A

    串联

    B

    表决

    C

    旁联

    D

    桥联


    正确答案： B
    解析： 暂无解析

  • 第11题：

    单选题
    用DIMENSIONS（4，5）命令定义数组S后，再对各数组元素赋值：S（1，1）=1，S（1，2）=2，S（1，3）=3，S（1，4）=4，S（1，5）=5，S（2，1）=6，S（2，2）=7，S（2，3）=8，S（2，4）=9，S（2，5）=10，然后再执行命令？S（6），则显示结果是（）。
    A

    变量未定义的提示

    B

    4

    C

    6

    D

    F


    正确答案： D
    解析： 在Visual FoxPro中规定，数组是按行存取的，也就是本题中S（6）相当于S（2，1）=6，所以本题应选C。

  • 第12题：

    单选题
    若一个图的边集为{，，，，，}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（）。
    A

     1，2，5，4，3

    B

     1，2，3，4，5

    C

     1，2，5，3，4

    D

     1，4，3，2，5


    正确答案： A
    解析： 暂无解析

  • 第13题：

    已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为( )。

    A.V1V2V4V8V5V3V6V7

    B.V1V2V4V5V8V3V6V7

    C.V1V2V4V8V3V5V6V7

    D.V1V3V6V7V2V4V5V8


    参考答案：A


  • 第14题：


    A.{(1，4)，(2，3)，(2，5)}
    B.{(3，5)，(3，4)，(4，5)}
    C.{(1，3)，(3，4)，(3，5)}
    D.{(2，3)，(3，4)，(2，5)}

    答案：A
    解析：

  • 第15题：

    若已知有向图G=（V，E），其中，顶点的集合为V={v1，v2，v3，v4，v5}，弧的集合为E={， ，，，，}，则G的拓扑序列有哪些？（写出结论即可）


    正确答案:G的拓扑序列有3个，分别是v1,v2,v3,v4,v5；v1,v3,v2,v4,v5和v1,v3,v4,v2,v5。

  • 第16题：

    已知一个无向图顶点有5个，则边可能有（）个。

    • A、10
    • B、11
    • C、8
    • D、9

    正确答案:A,C,D

  • 第17题：

    假定一个有向图的边集为{，，< c，f>，< d，c>，< e，b>，< e，d>}，对该图进行拓扑排序得到的顶点序列为（）


    正确答案:aebdcf

  • 第18题：

    已知无向图G描述如下： G=（V，E） V={V1，V2，V3，V4，V5} E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）} 写出每个顶点的度。


    正确答案:V1、V2、V3、V4、V5的度分别为：2，3，2，3，2。

  • 第19题：

    填空题
    假定一个有向图的顶点集为{a，b，c，d，e，f}，边集为{， ， ， ， ， }，则出度为0的顶点个数为（），入度为1的顶点个数为（）

    正确答案： 2,4
    解析： 暂无解析

  • 第20题：

    问答题
    若已知有向图G=（V，E），其中，顶点的集合为V={v1，v2，v3，v4，v5}，弧的集合为E={， ，，，，}，则G的拓扑序列有哪些？（写出结论即可）

    正确答案： G的拓扑序列有3个，分别是v1,v2,v3,v4,v5；v1,v3,v2,v4,v5和v1,v3,v4,v2,v5。
    解析： 暂无解析

  • 第21题：

    单选题
    下列属于图G=（V，E）所必须包含的基本要素的是（）
    A

    边集

    B

    子图

    C

    关联边

    D

    基础图


    正确答案： B
    解析： 暂无解析

  • 第22题：

    问答题
    已知无向图G描述如下： G=（V，E） V={V1，V2，V3，V4，V5} E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）} 写出每个顶点的度。

    正确答案： V1、V2、V3、V4、V5的度分别为：2，3，2，3，2。
    解析： 暂无解析

  • 第23题：

    填空题
    若一个图的顶点集为{a，b，c，d，e，f}，边集为{（a，b），（a，c），（b，c），（d，e）}，则该图含有（）个连通分量。

    正确答案： 3
    解析： 暂无解析

相关内容