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

最小生成树(1)

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

一、定义

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













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

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

分享给朋友:

相关文章

【算法】分治算法

前言所谓分治算法就是指分而治之,即将较大规模的问题分解成几个较小规模的问题,通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。比如,我们玩过最简单的猜...

【题解】小X玩游戏

【题目描述】小X喜欢玩游戏。  这天,小X觉得传统的游戏都玩腻了,自己随手在草稿纸上画了一行N个格子作为棋盘, 制定了如下规则:格子从左到右依次编号为1到N,玩家初始位于格子1,初...

DEVC++中的快捷键

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

取模运算总结——数论

编程竞赛有相当一部分题目的结果过于庞大,整数类型无法存储,往往只要求输出取模的结果。例如(a+b)%p,若a+b的结果我们存储不了,再去取模,结果显然不对,我们为了防止溢出,可以先分别对a取模,b取模...

【入门篇】>>> DEVC++下载、安装、简单使用

【入门篇】>>> DEVC++下载、安装、简单使用

什么是DEVC++    DEVC++是一款编程工具,是一个Windows环境下的一个适合于初学者使用的轻量级C/C++ 集成开发环境(IDE),它是一款自由软件,遵守G...

C++中的溢出

一、编程中的溢出   溢出是C++语言中最常见的漏洞。最常见的溢出包括数组溢出、数溢出、缓冲区溢出、指针溢出以及栈溢出。二、数组溢出    ...