题库
  • 题库
  • 考试

移动端

  • 题王微信公众号

    题王微信公众号

    微信搜“题王网”真题密题、最新资讯、考试攻略、轻松拿下考试

首页 / 学历语言类/ 本科/ 计算机科学与技术 / 当前试题

单选题

分享题目

任何一个无向连通图的最小生成树（）。

发布日期：2021-03-18

任何一个无向连通图的最小生成树（）。
A

至少有一棵

B

只有一棵

C

一定有多棵

D

可能不存在

试题解析

最小生成树

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

中文名
最小生成树
提出者
Kruskal（克鲁斯卡尔）Prim（普里姆）
应用学科
计算机，数学（图论），数据结构
外文名
Minimum Spanning Tree,MST
适用领域
应用图论知识的实际问题
算法
Kruskal算法，Prim算法

连通图

在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。

中文名
连通图
学科
数学
性质
连通性
外文名
connected graph
所属领域
图论
相关术语
无向图

标签： 连通 最小 生成

查看答案

题王网让考试变得更简单

扫码关注题王，更多免费功能准备上线！

此试题出现在

本科

计算机科学与技术

去刷题

其他考试

专科 技术监督质检职业技能考试 一级造价工程师 国际商务师 儿科住院医师 水利监理工程师 注册化工工程师 中医耳鼻咽喉科住院医师 价格鉴证师 注册土木工程师（岩土）
热门试题热门资讯 相关试题

电动转辙机故障电流的变化与（）有关。

在“此说甚戾”中，“戾”的意义是：

把电气设备的外壳与零线连接起来，称为（）

绿色设计的核心

ZK4型电空转辙机活塞杆行程是多少？

试述JZ--7型空气制动机自阀客货车转换阀的转换方法。

下列属于垃圾回收再利用的基本方法是（）。

下列哪些指标已列入IC.SH电子血细胞计数仪性能评价范围：（）

下列哪些是鳃裂囊肿CT征象（　）

高速铁路引入既有枢纽的方式，按其引入线的平，纵断面不同，有三种引入方式，下面哪一种不是这三种引入方式的（）

暂无相关推荐~

任何一个无向连通图的最小生成树（）。

任何一个无向连通图的最小生成树（）。

一个连通图的最小生成树（）。

任何一个无向连通图的最小生成树（）

由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。

若一个连通图中每个边上的权值均不同，则得到的最小生成树是（）（唯一/不唯一）的。

若连通网络上各边的权值均不相同，则该图的最小生成树有（）棵。

带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。

从带连数长度的连通图中生成的最小支撑树，叙述不正确的是（）

n个顶点的带权无向连通图的最小生成树包含（）个顶点。