最小生成树(Prim、Kruskal算法)整理版
pascal,我整理的,希望能帮助大家,包括了原理+代码+优化代码
一、树及生成树的基本概念
树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述：
(1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。
例如：已知有六个城市，它们之间要架设电话线，要求任
意两个城市均可以互相通话，并且电话线的总长度最短。若用
六个点v1…v6代表这六个城市，在任意两个城市之间架设电话
线，即在相应的两个点之间连一条边。这样，六个城市的一个
电话网就作成一个图。任意两个城市之间均可以通话，这个图
必须是连通图，且这个图必须是无圈的。否则，从圈上任意去
掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是
一个不含圈的连通图，代表了一个电话线网。
生成树（支撑树）
定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。
定理：一个图G有生成树的条件是G是连通图。
证明:必要性显然；
充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子图GK，且不含圈，从而GK是一个生成树。
寻找连通图生成树的方法：
破圈法：从图中任取一个圈，去掉一条边。再对剩下的图
重复以上步骤，直到不含圈时为止，这样就得到一个生成树。
取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图
中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3）
中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，
这样，剩下的图不含圈，于是得到一个支撑树，如图所示。
避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。
你可能喜欢
- 最小生成树算法实现
- 算法合集
- 数据结构课程设计最小生成树
- 离散数学试题答案
- 拓扑排序算法
- 二叉树遍历
- 普里姆算法最小生成树
- 最短路径算法
- 用c语言实现prim算法k算法生成最小主树3页
- 最小生成树的Kruskal算法实现5页
- 最小生成树算法的快速实现2页
- 最小生成树算法实现2页
- 分别利用prim算法和kruskal算法实现求图的最小生成树9页
- 遗传算法最小生成树的实现13页
- 经典ACM算法合集经典ACM算法合集14页
- 遗传算法合集3页
- 算法合集之《信息学竞赛中的思维方法》8页
- 算法合集之《偶图的算法及应用》13页
- 算法合集之《遗传算法的特点及其应用》21页
- 算法合集之《论对题目中算法的选择》4页
- 《数据结构》课程设计 普里姆算法 最小生成树4页
- 数据结构课程设计报告(最小生成树完整版)7页
- 数据结构最小生成树课程设计21页
- 数据结构课程设计报告最小生成树Kruskal算法28页
- 数据结构课程设计最小生成树问题10页
- 数据结构课程设计-最小生成树17页
- 2010年7月全国自考离散数学试题参考答案4页
- 离散数学期末考试试题(有几套带答案)11页
- 《离散数学》试题及答案1页
- 2009年4月自学考试离散数学试题(附答案)7页
- 电大离散数学试题与答案2003年7月6页
- 离散数学试题B答案4页
- 【数据结构算法】实验9 图的拓扑排序问题(附源代码)9页
- 图算法(2) --拓扑排序,2-SAT,欧拉路 - TOJ41页
- 一种有向权图的拓扑排序算法及其应用4页
- 拓扑排序算法实现(3)1页
- 拓扑排序算法4页
- 贪婪算法--- 拓扑排序4页
- 实验四 二叉树遍历3页
- 二叉树遍历 program9页
- 二叉树遍历报告3页
- 二叉树遍历程序4页
- 二叉树遍历17页
- 数据结构：二叉树遍历的实现6页
