树与图的最小树

最小树的名词解释最小树是图论中的一个概念，它是指在一个连通的无向图中，通过选择最少的边将所有的顶点连接起来的一棵树。

最小树通常用于解决最优路径问题和网络设计等领域，它能够在保证所有顶点连通的前提下，使整个图的总权重最小。

为了更好地理解最小树的概念，我们可以通过一个简单的例子来说明。

假设我们有一个无向图，其中有四个顶点A、B、C和D，以及相应的边AB、AC、AD、BC、BD和CD。

现在的问题是如何通过选择最少的边，将所有的顶点连接起来。

为了解决这个问题，我们可以使用Kruskal算法或Prim算法来构建最小树。

这两种算法在解决最小树问题上非常有效。

在Kruskal算法中，首先将所有边按照权重从小到大进行排序。

之后，依次从最小权重的边开始选择，但要保证所选择的边不会形成环路。

当所有的顶点都被连接起来，即形成一棵树时，这棵树就是最小树。

而在Prim算法中，则是从一个初始顶点开始，逐渐将与该顶点相连的边加入最小树中，直到所有的顶点都被连接起来。

无论是Kruskal算法还是Prim算法，它们都能够快速地找到最小树。

通过这种方式，我们可以在保证图的连通性的前提下，选择最少的边来构建一棵最小树。

最小树不仅仅在图论中有应用，它也可以被应用在其他领域。

例如，最小树经常被用于解决计算机网络设计中的问题。

在设计网络拓扑结构时，我们希望通过尽可能少的连接来保证所有节点之间的可达性和通信效率。

使用最小树可以帮助我们找到一个经济高效的网络设计方案。

此外，最小树还可以用于解决最优路径问题。

在网络路由或交通规划中，我们经常需要找到一条连接所有目标点的最短路径。

使用最小树可以帮助我们找到连接所有目标点的最短路径，从而提高路由的效率和减少通信成本。

总之，最小树是图论中一个重要的概念，它通过选择最少的边来保证图的连通性，并在此过程中使整个图的总权重最小。

最小树不仅仅在图论领域有应用，它还可以被广泛应用于网络设计和最优路径问题等领域。

156运筹学图6.17 生成树此时41k E V ==−+，这样得到了生成树。

6.2.3 最小树最小树是网络优化中的一个重要概念，在交通网、电力网、通讯网等的设计中均有广泛的应用。

定义6.2.3 设连通图G V E =（，）。

每条边i j e v v =（，）上都有一个非负权数ij w e w =（）。

若1T V E =（，）是G 的一个生成树，则称1E 中所有边的权之和为生成树T 的权，记为()ij w T w =∑。

称具有最小权的生成树为G 的最小生成树，简称为最小树。

显然，对于最小树，有如下结论成立。

定理6.2.2 若把连通网络图的所有点分成V 和V 两个集合，则两集合之间连线的最短边一定包含在最小树内。

下面介绍如何寻找或构建一个最小树的几种算法。

算法1 Kruskal 算法1956年Kruskal 给出了求最小树问题的一种算法。

其基本思想是从网络中逐步挑选边构成最小生成树。

每次挑选的边对应的权要尽可能小，但必须保证已选好的边不产生圈。

这种方法称为Kruskal 算法，也称为避圈法。

这种方法与求生成树的避圈法类似。

避圈法步骤如下。

Step1 把图中的所有顶点分成V 和V 两个集合。

从图中任选一点i v ，让i v V ∈，图中其余点均包含在V 中。

Step2 从V 和V 的连线中找出最小边，这条边一定包含在最小树内，不妨设最小边为i j v v （，），将i j v v （，）标记成最小树内的边。

令{}j V V v =∪，{}\j V V v =。

Step3 若V =Φ，则算法终止。

否则转入Step2。

例6.6 一个乡有9个自然村，其间道路及各个道路长度如图6.18所示，各边上的数表示距离，问如何拉线才能使用线最短。

解 用Kruskal 算法。

Step1 令{}1V v =，{}02345678V v v v v v v v v =，，，，，，，。

Step2 {}12101818min 1w w w w ==，，。

图的steiner最小树问题及其求解作者：杨凌云来源：《电脑知识与技术》2009年第25期摘要:斯坦纳树问题是组合优化学科中的一个问题。

属于NP-难问题,即无法在多项式时间内得到最优解。

本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。

最后对算法进行了分析。

关键词:Steiner最小树 NP-难题破圈法中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)25-7312-02Graphical Steiner Minimum Tree Problem and SolusionYANG Ling-yun(College of Computer and Information Engineering, Henan University, Kaifeng 475001,China)Abstract: Steiner tree problem is one of the subject of combinatorial optimization problem. It belongs to NP-hard problems that cann’t find the optimal solution in polynomial time. This article discusses the minimum steiner tree problem in graphs, and gives the approximate algorithm, which is improved on loop damage method, and quoted the agent's thinking. Finally, an analysis of the algorithm.Key words: steiner minimum tree; NP-hard problem; loop damage method现实生活中经常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。

最小树与最小树形图（数学建模）讲解一、最小树的定义及性质1. 定义：最小树，又称最小树，是指在给定的带权无向图中，包含图中所有顶点的一个树形结构，且树中所有边的权值之和最小。

2. 性质：（1）最小树中不存在回路；（2）对于最小树中的任意两个顶点，它们之间有且仅有一条路径；（3）最小树中边的数量等于顶点数量减一；（4）在最小树中添加任意一条边，都会形成一条回路；（5）最小树不唯一，但权值之和相同。

二、求解最小树的方法1. Prim算法Prim算法是一种贪心算法，其基本思想是从图中的一个顶点开始，逐步添加边和顶点，直到形成最小树。

具体步骤如下：（1）初始化：选择一个顶点作为最小树的起点，将其加入最小树集合；（2）迭代：在最小树集合和非最小树集合之间，寻找一条权值最小的边，将其加入最小树集合；（3）重复步骤2，直到所有顶点都加入最小树集合。

2. Kruskal算法Kruskal算法同样是一种贪心算法，其基本思想是将图中的所有边按权值从小到大排序，然后依次选择权值最小的边，判断是否形成回路，若不形成回路，则将其加入最小树集合。

具体步骤如下：（1）初始化：将所有顶点视为独立的树；（2）按权值从小到大排序所有边；（3）迭代：选择权值最小的边，判断其是否形成回路，若不形成回路，则将其加入最小树集合；（4）重复步骤3，直到所有顶点都在同一棵树中。

三、最小树形图的定义及求解方法1. 定义：最小树形图，又称最优树形图，是指在给定的有向图中，找到一个包含所有顶点的树形结构，使得树中所有边的权值之和最小。

2. 求解方法：朱刘算法（Edmonds' Algorithm）朱刘算法是一种用于求解最小树形图的算法，其基本思想是通过寻找图中的最小权值环，进行收缩和扩展操作，最终得到最小树形图。

具体步骤如下：（1）寻找最小权值环；（2）对最小权值环进行收缩操作，将环中的顶点合并为一个新顶点；（3）在新图中寻找最小树形图；（4）将新图中的最小树形图扩展回原图，得到原图的最小树形图。

图 论哥尼斯堡七桥问题：图论发源于18世纪普鲁士的哥尼斯堡。

普雷格河流经这个城市，河中有两个小岛，河上有七座桥，连接两岛及两岸。

如图所示，当时城里居民热衷于讨论这样一个问题：一个人能否走过这七座桥，且每座桥只经过一次，最后仍回到出发点。

将上面问题中的两座小岛以及两岸用点表示，七座桥用线（称为边）表示，得到下图：于是，上述问题也可叙述为：寻找从图中的任意一个点出发，经过所有的边一次且仅一次并回到出发点的路线。

注意：在上面的图中，我们只关心点之间是否有边相连，而不关心点的具体位置，边的形状以及长度。

一、基本概念：图：由若干个点和连接这些点中的某些“点对”的连线所组成的图形。

顶点：上图中的A ，Ｂ，Ｃ，D ．常用表示。

n 21 v , , v , v 边：两点间的连线。

记为（Ａ，Ｂ），（Ｂ，Ｃ）．常用表示。

m 21e , , e , e次：一个点所连的边数。

定点ｖ的次记为d(v)．图的常用记号：Ｇ＝（Ｖ，Ｅ），其中，}{v V i =，}{e E i =子图：图Ｇ的部分点和部分边构成的图，成为其子图。

路：图Ｇ中的点边交错序列，若每条边都是其前后两点的关联边，则称该点边序列为图Ｇ的一条链。

圈（回路）：一条路中所含边点均不相同，且起点和终点是同一点，则称该路为圈（回路）。

有向图：，其中(,)G N A =12{,,,}k N n n n = 称为的顶点集合，A a 称为G 的弧集合。

G {(,)ij i j }n n ==若，则称为的前驱， 为n 的后继。

(,)ij i j a n n =i n j n j n i 赋权图（网络）：设是一个图，若对G 的每一条边（弧）都赋予一个实数，称为边的权，。

记为。

G (,,)G N E W =两个结论：１、图中所有顶点度数之和等于边数的二倍； ２、图中奇点个数必为偶数。

二、图的计算机存储：1. 关联矩阵简单图：，对应(,)G N E =N E ×阶矩阵()ik B b =10ik i k b ⎧=⎨⎩点与边关联否则简单有向图：，对应(,)G N A =N A ×阶矩阵()ik B b =110ik ik ik a i b a i ⎧⎪=−⎨⎪⎩弧以点为尾弧以点为头否则2. 邻接矩阵简单图：，对应(,)G N E =N N ×阶矩阵()ij A a =10ij i j a ⎧=⎨⎩点与点邻接否则简单有向图：，对应(,)G N A =N N ×阶矩阵()ij A a =10ij i ja ⎧=⎨⎩有弧从连向否则5v 34v01010110100101011110101000110111101065432166654321⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=×v v v v v v A v v v v v v3. 权矩阵：简单图：，对应(,)G N E =N N ×阶矩阵()ij A a =ij ij i j a ω⎧=⎨∞⎩点与点邻接否则123456781234567802130654.5061002907250473080 v v v v v v v v v v v v v v v v 48∞∞∞∞⎡⎤⎢⎥∞∞∞∞∞⎢⎥⎢⎥∞∞∞∞∞⎢⎥∞∞∞∞∞⎢⎥⎢⎥∞∞∞∞⎢⎥∞∞∞∞⎢⎥⎢⎥∞∞∞∞⎢⎥∞∞∞∞∞∞⎢⎥⎣⎦三、图的应用：例：如图，用点代表7个村庄，边上的权代表村庄之间的路长，现在要在这7个村庄中布电话线，如何布线，使材料最省？分析：需要将图中的边进行删减，使得最终留下的图仍然连通，并且使总的权值最小。

求最小树的计算方法最小生成树是指在一个连通的无向图中，找到一棵生成树，使得这棵生成树的边权之和最小。

最小生成树问题是图论中的经典问题，有着广泛的应用。

目前，最小生成树问题有两种经典的算法：Prim算法和Kruskal算法。

1. Prim算法Prim算法是一种贪心算法，它从一个点开始，每次选择一条最短的边连接到已经选中的点集合中的一个点，直到所有的点都被选中，构成一棵生成树。

具体实现步骤如下：（1）初始化：选定一个起始点，将该点加入已选中的点集合中，将与该点相连的边加入边集合中。

（2）重复以下步骤，直到所有点都被选中：- 从边集合中选出一条权值最小的边，该边所连接的点如果已经被选中，则跳过该边，否则将该点加入已选中的点集合中，将与该点相连的边加入边集合中。

时间复杂度为O(ElogV)，其中E为边数，V为点数。

2. Kruskal算法Kruskal算法也是一种贪心算法，它从所有边中选取权值最小的边，如果该边所连接的两个点不在同一个连通分量中，则将这两个点所在的连通分量合并，直到所有点都在同一个连通分量中，构成一棵生成树。

具体实现步骤如下：（1）将所有边按照权值从小到大排序。

（2）初始化：将所有点看成一个连通分量。

（3）重复以下步骤，直到所有点都在同一个连通分量中：- 从排好序的边集合中选出一条权值最小的边，如果该边所连接的两个点在同一个连通分量中，则跳过该边，否则将这两个点所在的连通分量合并，将该边加入边集合中。

时间复杂度为O(ElogE)，其中E为边数。

以上就是最小生成树的两种经典算法，它们都是基于贪心策略的，但具体实现方式略有不同。

在实际应用中，可以根据具体情况选择合适的算法。

数据结构之最⼩⽣成树Prim算法普⾥姆算法介绍 普⾥姆（Prim）算法，是⽤来求加权连通图的最⼩⽣成树算法 基本思想：对于图G⽽⾔，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U⽤于存放G的最⼩⽣成树中的顶点，T存放G的最⼩⽣成树中的边。

从所有uЄU，vЄ(V-U) (V-U表⽰出去U的所有顶点)的边中选取权值最⼩的边(u, v)，将顶点v加⼊集合U中，将边(u, v)加⼊集合T中，如此不断重复，直到U=V为⽌，最⼩⽣成树构造完毕，这时集合T中包含了最⼩⽣成树中的所有边。

代码实现1. 思想逻辑 （1）以⽆向图的某个顶点（A）出发，计算所有点到该点的权重值，若⽆连接取最⼤权重值#define INF (~(0x1<<31)) （2）找到与该顶点最⼩权重值的顶点（B），再以B为顶点计算所有点到改点的权重值，依次更新之前的权重值，注意权重值为0或⼩于当前权重值的不更新，因为1是⼀当找到最⼩权重值的顶点时，将权重值设为了0，2是会出现⽆连接的情况。

（3）将上述过程⼀次循环，并得到最⼩⽣成树。

2. Prim算法// Prim最⼩⽣成树void Prim(int nStart){int i = 0;int nIndex=0; // prim最⼩树的索引，即prims数组的索引char cPrims[MAX]; // prim最⼩树的结果数组int weights[MAX]; // 顶点间边的权值cPrims[nIndex++] = m_mVexs[nStart].data;// 初始化"顶点的权值数组"，// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。

for (i = 0; i < m_nVexNum; i++){weights[i] = GetWeight(nStart, i);}for (i = 0; i < m_nVexNum; i ++){if (nStart == i){continue;}int min = INF;int nMinWeightIndex = 0;for (int k = 0; k < m_nVexNum; k ++){if (weights[k]!= 0 && weights[k] < min){min = weights[k];nMinWeightIndex = k;}}// 找到下⼀个最⼩权重值索引cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data;// 以找到的顶点更新其他点到该点的权重值weights[nMinWeightIndex]=0;int nNewWeight = 0;for (int ii = 0; ii < m_nVexNum; ii++){nNewWeight = GetWeight(nMinWeightIndex, ii);// 该位置需要特别注意if (0 != weights[ii] && weights[ii] > nNewWeight){weights[ii] = nNewWeight;}}for (i = 1; i < nIndex; i ++){int min = INF;int nVexsIndex = GetVIndex(cPrims[i]);for (int kk = 0; kk < i; kk ++){int nNextVexsIndex = GetVIndex(cPrims[kk]);int nWeight = GetWeight(nVexsIndex, nNextVexsIndex);if (nWeight < min){min = nWeight;}}nSum += min;}// 打印最⼩⽣成树cout << "PRIM(" << m_mVexs[nStart].data <<")=" << nSum << ": ";for (i = 0; i < nIndex; i++)cout << cPrims[i] << "";cout << endl;}3. 全部实现#include "stdio.h"#include <iostream>using namespace std;#define MAX 100#define INF (~(0x1<<31)) // 最⼤值(即0X7FFFFFFF)class EData{public:EData(char start, char end, int weight) : nStart(start), nEnd(end), nWeight(weight){} char nStart;char nEnd;int nWeight;};// 边struct ENode{int nVindex; // 该边所指的顶点的位置int nWeight; // 边的权重ENode *pNext; // 指向下⼀个边的指针};struct VNode{char data; // 顶点信息ENode *pFirstEdge; // 指向第⼀条依附该顶点的边};// ⽆向邻接表class listUDG{public:listUDG(){};listUDG(char *vexs, int vlen, EData **pEData, int elen){m_nVexNum = vlen;m_nEdgNum = elen;// 初始化"邻接表"的顶点for (int i = 0; i < vlen; i ++){m_mVexs[i].data = vexs[i];m_mVexs[i].pFirstEdge = NULL;}char c1,c2;int p1,p2;ENode *node1, *node2;// 初始化"邻接表"的边for (int j = 0; j < elen; j ++){// 读取边的起始顶点和结束顶点p1 = GetVIndex(c1);p2 = GetVIndex(c2);node1 = new ENode();node1->nVindex = p2;node1->nWeight = pEData[j]->nWeight;if (m_mVexs[p1].pFirstEdge == NULL){m_mVexs[p1].pFirstEdge = node1;}else{LinkLast(m_mVexs[p1].pFirstEdge, node1);}node2 = new ENode();node2->nVindex = p1;node2->nWeight = pEData[j]->nWeight;if (m_mVexs[p2].pFirstEdge == NULL){m_mVexs[p2].pFirstEdge = node2;}else{LinkLast(m_mVexs[p2].pFirstEdge, node2);}}}~listUDG(){ENode *pENode = NULL;ENode *pTemp = NULL;for (int i = 0; i < m_nVexNum; i ++){pENode = m_mVexs[i].pFirstEdge;if (pENode != NULL){pTemp = pENode;pENode = pENode->pNext;delete pTemp;}delete pENode;}}void PrintUDG(){ENode *pTempNode = NULL;cout << "邻接⽆向表:" << endl;for (int i = 0; i < m_nVexNum; i ++){cout << "顶点:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->"; pTempNode = m_mVexs[i].pFirstEdge;while (pTempNode){cout <<pTempNode->nVindex << "->";pTempNode = pTempNode->pNext;}cout << endl;}}// Prim最⼩⽣成树void Prim(int nStart){int i = 0;int nIndex=0; // prim最⼩树的索引，即prims数组的索引char cPrims[MAX]; // prim最⼩树的结果数组int weights[MAX]; // 顶点间边的权值cPrims[nIndex++] = m_mVexs[nStart].data;// 初始化"顶点的权值数组"，// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。