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

最小生成树(1)

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

一、定义

一个有 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一共有两种选法,所以最小生成树有两个。













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

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

分享给朋友:

相关文章

c++ 如何用链表存取数据

c++ 如何用链表存取数据

由于单链表的每个结点都有一个数据域和一个指针域。所以,每个结点可以定义成一个记录。其中,DATA数据元素,可以为你想要储存的任何数据格式,可以是数组,可以是int,甚至可以是结构体(这就是传说中的结构...

质数(素数)的判断

一、定义法// 1 定义法(除了1和他本身之外,没有任何一个数能被整除)(试除法) bool is_prime3(unsigned long lon...

C++读取磁盘文件

0.前言简单介绍一下C++读取文件的基本操作。关键技术:freopen() 文件的打开函数 FILE *fp fp=fopen(文件名,使用文件方式) 例如: fp...

【数据结构】并查集1

【数据结构】并查集1

1.引入    对于一个集合S={a1, a2, …, an-1, an},我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm,我们希望能够快速确定...

指针(一):基础用法

1.定义什么是指针,简单来说:“指针就是地址”。2.指针变量的定义指针变量定义形式:  类型说明符  *变量名其中,*号表示指针变量。变量名即为定义的指针变量名,类型说明符表示该指...

【数论】组合数学—容斥原理

【数论】组合数学—容斥原理

概念在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重...