当前位置:首页 > C++知识 > 正文内容

最小生成树(1)

亿万年的星光7个月前 (08-31)C++知识924

一、定义

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


二、概述

在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此的权重,若存在 T 为 E 的子集且为无循环图,使得联通所有结点的的 w(T) 最小,则此 T 为 G 的最小生成树

最小生成树其实是最小权重生成树的简称。

三、生成树


要求最小生成树,先来理解什么是生成树。

生成树的定义:一个连通图的生成树是一个极小的连通子图,它包含图中全部的n个顶点,但只有构成一棵树的n-1条边。

可以看到一个包含3个顶点的完全图可以产生3颗生成树。那么对于包含n个顶点的无向完全图最多包含n^n-2 个生成树。


生成树的特点:


  • 一个连通图可以有多个生成树;

  • 一个连通图的所有生成树都包含相同的顶点个数和边数;

  • 生成树当中不存在环;

  • 移除生成树中的任意一条边都会导致图的不连通, 生成树的边最少特性;

  • 在生成树中添加一条边会构成环。

  • 对于包含n个顶点的连通图,生成树包含n个顶点和n-1条边


四、最小生成树

所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

比如上面这个,因为n个顶点的联通图,所以生成树包含n个顶点和n-1条边。

所以,很明显选3条边连起来肯定是1、2、3这个三个权重最小,那么1、2、3一共有两种选法,所以最小生成树有两个。













扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

2021 年青岛市程序设计竞赛试题(小学组)决赛

2021 年青岛市程序设计竞赛试题(小学组)决赛

1.方程求解【描述】输入正整数 a,b,c。求有多少组 x 和 y 满足 a*x+b*y=c 。x 和 y 都是非负整数。【输入】一行,包含三个正整数 a,b,c,两个整数之间用单个空格隔开。【输出】...

拓扑排序

拓扑排序

一、定义对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则...

进制转换类问题汇总

二进制转十进制十进制转二进制十进制转M进制(M一般小于16)M进制转十进制M进制和N进制互转...

深搜剪枝技巧

一、什么是剪枝     首先应当明确的是,“剪枝”的含义是什么。我们知道,搜索的进程可以看作是从树根出发,遍历一棵倒置的树——搜索树的过程。而所谓剪枝,顾名思义...

CSP-J2021年普及组复赛T4——小熊的果篮

【题目描述】    小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子,从左到右依 次用正整数 1、2、3、……、n 编号。连续排在一起的同一种...

DEVC++中的快捷键

快捷键可以帮我们加快速度,下面介绍一下我们经常用的快捷键。 Ctrl+A   全选Ctrl +C   复制Ctrl +V   粘贴...