最小生成树

最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）普⾥姆算法（Prim算法)思路：以点为⽬标构建最⼩⽣成树1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。

循环n-1次如下操作：（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标(2)打印此边，并将vk加⼊U中。

（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中以下图为例#include<bits/stdc++.h>using namespace std;#define MAXVEX 100#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;void CreateMGraph(MGraph *G) {int m, n, w; //vm-vn的权重wscanf("%d %d", &G->numVertexes, &G->numEdges);for(int i = 0; i < G->numVertexes; i++) {getchar();scanf("%c", &G->vexs[i]);}for(int i = 0; i < G->numVertexes; i++) {for(int j = 0; j < G->numVertexes; j++) {if(i == j) G->arc[i][j] = 0;else G->arc[i][j] = INF;}}for(int k = 0; k < G->numEdges; k++) {scanf("%d %d %d", &m, &n, &w);G->arc[m][n] = w;G->arc[n][m] = G->arc[m][n];}}void MiniSpanTree_Prim(MGraph G) {int min, j, k;int arjvex[MAXVEX]; //最⼩边在 U集合中的那个顶点的下标int lowcost[MAXVEX]; // 最⼩边上的权值//初始化,从点 V0开始找最⼩⽣成树Tarjvex[0] = 0; //arjvex[i] = j表⽰ V-U中集合中的 Vi点的最⼩边在U集合中的点为 Vjlowcost[0] = 0; //lowcost[i] = 0表⽰将点Vi纳⼊集合 U ，lowcost[i] = w表⽰ V-U中 Vi点到 U的最⼩权值for(int i = 1; i < G.numVertexes; i++) {lowcost[i] = G.arc[0][i];arjvex[i] = 0;}//根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩for(int i = 1; i < G.numVertexes; i++) {min = INF, j = 1, k = 0;//寻找 V-U到 U的最⼩权值minfor(j; j < G.numVertexes; j++) {// lowcost[j] != 0保证顶点在 V-U中，⽤k记录此时的最⼩权值边在 V-U中顶点的下标if(lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}}}printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);lowcost[k] = 0; //表⽰将Vk纳⼊ U//查找邻接矩阵Vk⾏的各个权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中for(int i = 1; i < G.numVertexes; i++) {if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {lowcost[i] = G.arc[k][i];arjvex[i] = k;}}}int main() {MGraph *G = (MGraph *)malloc(sizeof(MGraph));CreateMGraph(G);MiniSpanTree_Prim(*G);}/*input:4 5abcd0 1 20 2 20 3 71 2 42 3 8output:V[0]-V[1] weight = 2V[0]-V[2] weight = 2V[0]-V[3] weight = 7最⼩总权值: 11*/时间复杂度O(n^2)克鲁斯卡尔算法（Kruskal算法）思路：以边为⽬标进⾏构建最⼩⽣成树在边集中依次寻找最⼩权值边，若构建是不形成环路（利⽤parent数组记录各点的连通分量），则将其添加到最⼩⽣成树中。

最小生成树的概念
在图论中，最小生成树是一个连通图的生成树，其边的权值之和最小。

通俗地说，最
小生成树是指在一个图中找到一棵权值最小的生成树，这个生成树包含了连通图的所有顶点，且边的数量最小。

怎么找到最小生成树呢？有两种常用算法：Prim算法和Kruskal算法。

Prim算法首先任选一个点作为起点，然后在剩余的点中选择与当前集合距离最短的点加入集合，直到所有点被加入。

在加入每一个点时，找到与当前集合连接的距离最短的边，加入到生成树中。

重复以上步骤，直到所有点都被加入到生成树中。

Kruskal算法则是将边按照权值从小到大排序，选择权值最小的边加入到生成树中，
如果加入当前边后不构成环，则加入，否则继续找下一条权值最小的边。

重复以上步骤，
直到所有点都被加入到生成树中。

最小生成树有很广泛的应用，如在通信、传输、路网规划等领域都有很重要的作用。

在有些应用中，最小生成树不仅要求边的权值之和最小，还要满足一些约束条件，比如边
的数量、每个点的度数等，这时我们需要采用更加复杂的算法来求解问题。

最小生成树的应用非常广泛，比如在计算机网络中，路由协议需要找到最短的数据传
输路径；在城市交通中，规划出最优的交通路径能够有效减少能源的消耗；在电力系统中，设计最短的输电线路可以节省能源成本。

最小生成树的运用如此广泛，它不仅在计算机科
学中有重要作用，也在其他各个领域有着不可替代的作用。

最短路径与最小生成树的区别
在图论中，最短路径和最小生成树是两个重要的概念。

它们都是用来解决图中节点之间的距离问题，但是它们的解决方法和目的却有所不同。

最短路径问题是指在一个有向或无向加权图中，找到从一个节点到另一个节点最短的路径。

最短路径可以使用Dijkstra算法和Bellman-Ford算法来解决。

这类问题通常是求出从一个节点到其他节点的最短距离，通常用于网络路由、GPS导航等应用。

最小生成树问题是指在一个无向加权图中，找到一个生成树，使得该树中的所有边权之和最小。

最小生成树可以使用Prim算法和Kruskal算法来求解。

这类问题通常是在需要将图连接起来的场合，比如铺设电缆、通信网络等场合。

因此，最短路径问题和最小生成树问题虽然都与计算节点间距离有关，但是它们的解决方法和应用场景却有很大的差异。

在具体应用中，需要根据实际情况选择合适的算法和方法来解决问题。

- 1 -。

离散数学最小生成树例题（实用版）目录1.最小生成树的概念和性质2.最小生成树的算法原理3.最小生成树的算法举例4.最小生成树的应用实例正文一、最小生成树的概念和性质最小生成树（Minimum Spanning Tree，简称 MST）是指在一个加权连通图中，选择一些边，使得所有节点都能被联通，并且边代价之和最小。

最小生成树具有以下性质：1.树中的边是最短的边：在生成树中，任意两个节点之间的边都是最短的边，即不存在比这条边更短的边能连接这两个节点。

2.树是没有圈的：最小生成树显然不应该有圈，因为如果有圈，可以通过删除圈中的一条边来形成一个更小的生成树。

二、最小生成树的算法原理求解最小生成树的经典算法有 Kruskal 算法和 Prim 算法。

这里我们以 Prim 算法为例介绍最小生成树的算法原理。

Prim 算法的基本思想是从一个初始节点开始，不断地寻找与当前生成树距离最近的节点，将其加入到生成树中，直到所有节点都加入到生成树中为止。

在寻找距离最近的节点时，我们需要使用贪心策略，即每次都选择距离最近的节点。

为了判断一个节点是否已经加入了生成树，我们可以使用并查集数据结构。

三、最小生成树的算法举例这里我们以一个简单的例子来说明 Prim 算法的求解过程。

假设有一个图，共有 4 个节点，5 条边，边的权值分别为 1, 2, 3, 4, 5。

我们选择节点 1 作为初始节点，按照 Prim 算法的步骤，可以得到最小生成树的权值为 9，生成树如下所示：```1 --2 --3 -- 4```四、最小生成树的应用实例最小生成树在实际应用中有很多实例，如网络路由、数据压缩、图像处理等。

这里我们以网络路由为例，介绍最小生成树的应用。

在网络中，为了提高传输效率，我们需要在网络中建立一条最短路径。

通过求解最小生成树，我们可以得到网络中的最短路径，从而为数据包的传输提供指导。

在求解最小生成树时，我们可以将网络中的节点看作是图的顶点，边看作是图的边，边的权值看作是节点之间的距离。

最⼩⽣成树（普⾥姆算法）：所谓⽣成树，就是n个点之间连成n-1条边的图形。

⽽最⼩⽣成树，就是权值（两点间直线的值）之和的最⼩值。

⾸先，要⽤⼆维数组记录点和权值。

如上图所⽰⽆向图：int map[7][7];map[1][2]=map[2][1]=4;map[1][3]=map[3][1]=2;......然后再求最⼩⽣成树。

具体⽅法是：1.先选取⼀个点作起始点，然后选择它邻近的权值最⼩的点（如果有多个与其相连的相同最⼩权值的点，随便选取⼀个）。

如1作为起点。

visited[1]=1;pos=1;//⽤low[]数组不断刷新最⼩权值，low[i](0<i<=点数)的值为：i点到邻近点（未被标记）的最⼩距离。

low[1]=0; //起始点i到邻近点的最⼩距离为0low[2]=map[pos][2]=4;low[3]=map[pos][3]=2;low[4]==map[pos][4]=3;low[5]=map[pos][5]=MaxInt; //⽆法直达low[6]=map[pos][6]=MaxInt;2.再在伸延的点找与它邻近的两者权值最⼩的点。

//low[]以3作当前位置进⾏更新visited[3]=1;pos=3;low[1]=0; //已标记，不更新low[2]=map[1][2]=4; //⽐5⼩，不更新low[3]=2; //已标记，不更新low[4]=map[1][4]=3; //⽐1⼤，更新后为：low[4]=map[3][4]=1;low[5]=map[1][5]=MaxInt;//⽆法直达，不更新low[6]=map[1][6]=MaxInt;//⽐2⼤，更新后为：low[6]=map[3][6]=2;3.如此类推...当所有点都连同后，结果最⽣成树如上图所⽰。

所有权值相加就是最⼩⽣成树，其值为2+1+2+4+3=12。

⾄于具体代码如何实现，现在结合POJ1258例题解释。

最小生成树算法详解最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个经典问题，它是指在一个加权连通图中找出一棵包含所有顶点且边权值之和最小的树。

在解决实际问题中，最小生成树算法被广泛应用于网络规划、电力传输、城市道路建设等领域。

本文将详细介绍最小生成树算法的原理及常见的两种算法：Prim算法和Kruskal算法。

一、最小生成树算法原理最小生成树算法的核心思想是贪心算法。

其基本原理是从图的某个顶点开始，逐步选取当前顶点对应的边中权值最小的边，并确保选取的边不会构成环，直到所有顶点都被连接为止。

具体实现最小生成树算法的方法有多种，两种常见的算法是Prim 算法和Kruskal算法。

二、Prim算法Prim算法是一种基于顶点的贪心算法。

它从任意一个顶点开始，逐渐扩展生成树的规模，直到生成整个最小生成树。

算法的具体步骤如下：1. 初始化一个空的生成树集合和一个空的顶点集合，将任意一个顶点加入到顶点集合中。

2. 从顶点集合中选择一个顶点，将其加入到生成树集合中。

3. 以生成树集合中的顶点为起点，寻找与之相邻的顶点中权值最小的边，并将该边与对应的顶点加入到最小生成树中。

4. 重复第3步，直到生成树中包含所有顶点。

Prim算法是一种典型的贪心算法，其时间复杂度为O(V^2)，其中V为顶点数。

三、Kruskal算法Kruskal算法是一种基于边的贪心算法。

它首先将所有边按照权值从小到大进行排序，然后从小到大依次选择边，判断选取的边是否与已选取的边构成环，若不构成环，则将该边加入到最小生成树中。

算法的具体步骤如下：1. 初始化一个空的生成树集合。

2. 将图中的所有边按照权值进行排序。

3. 依次选择权值最小的边，判断其两个顶点是否属于同一个连通分量，若不属于，则将该边加入到最小生成树中。

4. 重复第3步，直到最小生成树中包含所有顶点。

Kruskal算法通过并查集来判断两个顶点是否属于同一个连通分量，从而避免形成环。

欧拉定律（Euler's Law）欧拉定律是由瑞士数学家欧拉（Leonhard Euler）在18世纪中叶提出的一个重要定律。

它描述了在一个连通的平面图中，顶点的度数（即与该顶点相连的边的数量）的性质。

根据欧拉定律，一个连通的平面图中满足以下条件：若图中有一个或多个顶点的度数为奇数，则此图不是欧拉图（Eulerian graph）；若所有顶点的度数都为偶数，则此图是欧拉图。

对于一个连通平面图，它至少存在一条欧拉路径（Eulerian path），即从某个顶点开始，沿着边行走，可以遍历图中所有边且各边只经过一次。

（欧拉路径可以从任意顶点出发）对于一个连通平面图，要满足存在欧拉回路（Eulerian circuit），即从某个顶点出发，可以遍历图中所有边且各边只经过一次，并最终回到出发顶点。

最小生成树（Minimum Spanning Tree）最小生成树是在一个无向连通图中，选择连通所有顶点的一棵树，并使得树的所有边权重之和最小的一种树结构。

最小生成树问题通常用于求解网络、运输和通信等领域中的优化问题。

常用的算法包括Prim算法和Kruskal算法。

Prim算法（Prim's Algorithm）: 从一个起始顶点开始，每次选择与已选顶点集合最近的一个顶点，并将其加入集合，直到所有顶点被加入。

Kruskal算法（Kruskal's Algorithm）: 将边按照权重从小到大排序，逐个加入到生成树中，只要边加入不构成闭合回路即可。

最小生成树的应用广泛，比如在通信网络中优化传输成本、在城市规划中优化建设成本等。

它可以帮助我们找到满足条件的连通子图，在保证最小总成本的前提下建立起高效的连接关系。