下载文档原格式
最⼩⽣成树的Prim算法以及Kruskal算法的证明Prime算法的思路：从任何⼀个顶点开始，将这个顶点作为最⼩⽣成树的⼦树，通过逐步为该⼦树添加边直到所有的顶点都在树中为⽌。
其中添加边的策略是每次选择外界到该⼦树的最短的边添加到树中（前提是⽆回路）。
Prime算法的正确性证明：引理1：对于连通图中的顶点vi，与它相连的所有边中的最短边⼀定是属于最⼩⽣成树的。
引理2：证明：假设最⼩⽣成树已经建成；(vi, vj)是连接到顶点vi的最短边，在最⼩⽣成树中取出vi，断开连接到vi的边，则⽣成树被拆分成1、顶点vi2、顶点vj所在的连通分量（单独⼀个顶点也看作⼀个独⽴的连通分量）3、其余若⼲个连通分量（个数⼤于等于0）三个部分现在要重建⽣成树，就要重新连接之前被断开的各边虽然不知道之前被断开的都是哪⼏条边，但是可以通过这样⼀个简单的策略来重建连接：将vi分别以最⼩的成本逐个连接到这若⼲个互相分离的连通分量；具体来说，就是要分别遍历顶点vi到某个连通分量中的所有顶点的连接，然后选择其中最短的边来连接vi和该连通分量；⽽要将vi连接到vj所在的连通分量，显然通过边(vi, vj)连接的成本最低，所以边(vi, vj)必然属于最⼩⽣成树（如果连接到vi的最短边不⽌⼀条，只要任意挑选其中的⼀条(vi, vj)即可，以上的证明对于这种情况同样适⽤）。
这样我们就为原来只有⼀个顶点vi的⼦树添加了⼀个新的顶点vj及新边(vi, vj)；接下来只要将这棵新⼦树作为⼀个连通⼦图，并且⽤这个连通⼦图替换顶点vi重复以上的分析，迭代地为⼦树逐个地添加新顶点和新边即可。
Kruskal算法：通过从⼩到⼤遍历边集，每次尝试为最⼩⽣成树加⼊当前最短的边，加⼊成功的条件是该边不会在当前已构建的图中造成回路，当加⼊的边的数⽬达到n-1，遍历结束。
Kruskal算法的正确性证明：Kruskal算法每次为当前的图添加⼀条不会造成回路的新边，其本质是逐步地连接当前彼此分散的各个连通分量（单个顶点也算作⼀个连通分量），⽽连接的策略是每次只⽤最⼩的成本连接任意两个连通分量。
最⼩⽣成树---普⾥姆算法（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算法普⾥姆算法—Prim算法算法思路：⾸先就是从图中的⼀个起点a开始，把a加⼊U集合，然后，寻找从与a有关联的边中，权重最⼩的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加⼊到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最⼩的那条边并且该边的终点在集合：（V-U）中，我们把c加⼊到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了，⼀次类推，直到所有顶点都加⼊到了集合U。
（普⾥姆算法是允许负数的，狄杰斯特拉算法不⽀持）下⾯我们对下⾯这幅图求其最⼩⽣成树：1.假设我们从顶点v1开始，所以我们可以发现（v1,v3）边的权重最⼩，所以第⼀个输出的边就是：v1—v3=1:2.然后，我们要从v1和v3作为起点的边中寻找权重最⼩的边，⾸先了（v1,v3）已经访问过了，所以我们从其他边中寻找，发现(v3,v6)这条边最⼩，所以输出边就是：v3—-v6=43.然后，我们要从v1、v3、v6这三个点相关联的边中寻找⼀条权重最⼩的边，我们可以发现边(v6,v4)权重最⼩，所以输出边就是：v6—-v4=2.4.然后，我们就从v1、v3、v6、v4这四个顶点相关联的边中寻找权重最⼩的边，发现边（v3，v2）的权重最⼩，所以输出边：v3—–v2=55.然后，我们就从v1、v3、v6、v4，v2这2五个顶点相关联的边中寻找权重最⼩的边，发现边（v2，v5）的权重最⼩，所以输出边：v2—–v5=36.最后，我们发现六个点都已经加⼊到集合U了，我们的最⼩⽣成树建⽴完成。
Prim算法#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#define MAX 100#define INF (~(0x1<<31))typedef struct Graph{char vexs[MAX];int vexnum;int edgnum;int matrix[MAX][MAX];} Graph,*PGraph;typedef struct EdgeData{char start;char end;int weight;} EData;static int get_position(Graph g,char ch){int i;for(i=0; i<g.vexnum; i++)if(g.vexs[i]==ch)return i;return -1;}Graph* create_graph(){char vexs[]= {'A','B','C','D','E','F','G'};int matrix[][7]={{0,12,INF,INF,INF,16,14},{12,0,10,INF,INF,7,INF},{INF,10,0,3,5,6,INF},{INF,INF,3,0,4,INF,INF},{INF,INF,5,4,0,INF,8},{16,7,6,INF,2,0,9},{14,INF,INF,INF,8,9,0}};int vlen=sizeof(vexs)/sizeof(vexs[0]);int i,j;Graph *pG;if((pG=(Graph*)malloc(sizeof(Graph)))==NULL) return NULL;memset(pG,0,sizeof(pG));pG->vexnum=vlen;for(i=0; i<pG->vexnum; i++)pG->vexs[i]=vexs[i];for(i=0; i<pG->vexnum; i++)for(j=0; j<pG->vexnum; j++)pG->matrix[i][j]=matrix[i][j];for(i=0; i<pG->vexnum; i++){for(j=0; j<pG->vexnum; j++){if(i!=j&&pG->matrix[i][j]!=INF)pG->edgnum++;}}pG->edgnum/=2;return pG;}void print_graph(Graph G){int i,j;printf("Matrix Graph: \n");for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)printf("%10d ",G.matrix[i][j]);printf("\n");}}EData* get_edges(Graph G){EData *edges;edges=(EData*)malloc(G.edgnum*sizeof(EData)); int i,j;int index=0;for(i=0; i<G.vexnum; i++){for(j=i+1; j<G.vexnum; j++){if(G.matrix[i][j]!=INF){edges[index].start=G.vexs[i];edges[index].end=G.vexs[j];edges[index].weight=G.matrix[i][j];index++;}}}return edges;}void prim(Graph G,int start){int min,i,j,k,m,n,sum;int index=0;char prim[MAX];int weight[MAX];prim[index++]=G.vexs[start];for(i=0; i<G.vexnum; i++)weight[i]=G.matrix[start][i];weight[start]=0;for(i=0; i<G.vexnum; i++){//i⽤来控制循环的次数，每次加⼊⼀个结点，但是因为start已经加⼊，所以当i为start是跳过 if(start==i)continue;j=0;k=0;min=INF;for(k=0; k<G.vexnum; k++){if(weight[k]&&weight[k]<min){min=weight[k];j=k;}}sum+=min;prim[index++]=G.vexs[j];weight[j]=0;for(k=0; k<G.vexnum; k++){if(weight[k]&&G.matrix[j][k]<weight[k])weight[k]=G.matrix[j][k];}}// 计算最⼩⽣成树的权值sum = 0;for (i = 1; i < index; i++){min = INF;// 获取prims[i]在G中的位置n = get_position(G, prim[i]);// 在vexs[0...i]中，找出到j的权值最⼩的顶点。
随机prim算法Prim算法是一种普遍使用的最小生成树算法，它可以在图中找到一棵树，从而使得该树中所有边的权值之和最小。
Prim算法的基本思想是从一个顶点开始，逐步扩张最小生成树，每次向树中加入一条边，使得该边连接树上的节点和未加入树中的节点，并且权值最小。
这个过程中需要不断更新已加入树中的节点和未加入树中的节点之间的距离。
Prim算法的流程如下：1.选择一个起始顶点，将其加入到最小生成树中。
2.接着，将这个顶点可以到达的所有节点，以及它们之间的边加入到一个优先队列中。
其中，边的权值为该边连接的两个顶点值的较小值。
3.从优先队列中弹出权值最小的边，判断该边连接的两个顶点是否已经在最小生成树中，如果一个顶点已经在最小生成树中，而另外一个不在，则将未加入树中的节点和该边加入到最小生成树中。
5.重复步骤3和4，直到所有的节点都在最小生成树中。
下面是一个简单的Prim算法实例，我们来看一下：```Pythonimport heapqdef prim(graph, start):mst = [] # 保存最小生成树visited = [] # 保存已经访问的节点heap = [] # 优先队列while heap:# 找到权值最小的边w, u, v = heapq.heappop(heap)if v in visited:continuevisited.append(v)mst.append((u, v, w))return mst# 测试graph = {'A': {'B': 7, 'D': 5},'B': {'A': 7, 'C': 8, 'D': 9, 'E': 7},'C': {'B': 8, 'E': 5},'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},'E': {'B': 7, 'C': 5, 'D': 15, 'F': 8, 'G': 9},'F': {'D': 6, 'E': 8, 'G': 11},'G': {'E': 9, 'F': 11}}print(prim(graph, 'A')) # 输出：[('A', 'D', 5), ('D', 'F', 6), ('F', 'E', 8), ('E', 'C', 5), ('E', 'G', 9), ('A', 'B', 7)]```在以上实例中，我们使用了Python中的heapq模块，实现了Prim算法，以求得给定图的最小生成树。
prim算法c语言什么是Prim算法？Prim算法，也叫普里姆算法，是一种用于求解最小生成树的贪心算法。
最小生成树是指在一个无向连通图中，连接所有节点且边权值之和最小的树。
Prim算法的基本思想是从一个起始节点开始，每次选择与当前已经构建好的部分形成的子图相连的、权值最小的边所连接的节点，并将该节点加入到已经构建好的部分中。
直到所有节点都被加入到已经构建好的部分中，此时得到了一棵最小生成树。
Prim算法步骤1. 选定一个起点作为已经构建好的部分。
2. 将与该起点相连且未被访问过的边加入到候选集合中。
3. 从候选集合中选择一条权值最小的边连接到未被访问过的节点，并将该节点加入到已经构建好的部分中。
4. 将新加入节点所连接且未被访问过的边加入到候选集合中。
5. 重复步骤3和步骤4，直至所有节点都被加入到已经构建好的部分中。
Prim算法C语言实现下面给出Prim算法C语言实现代码：```#include <stdio.h>#include <stdlib.h>#include <limits.h>#define MAX_VERTICES 100#define INF INT_MAXtypedef struct {int weight;int visited;} Vertex;typedef struct {int vertices[MAX_VERTICES][MAX_VERTICES]; int num_vertices;} Graph;void init_graph(Graph *graph, int num_vertices) {graph->num_vertices = num_vertices;for (int i = 0; i < num_vertices; i++) {for (int j = 0; j < num_vertices; j++) {graph->vertices[i][j] = INF;}}}void add_edge(Graph *graph, int u, int v, int weight) { graph->vertices[u][v] = weight;graph->vertices[v][u] = weight;}void prim(Graph *graph) {Vertex vertices[MAX_VERTICES];for (int i = 0; i < graph->num_vertices; i++) {vertices[i].weight = INF;vertices[i].visited = 0;}vertices[0].weight = 0;for (int i = 0; i < graph->num_vertices - 1; i++) {// 找到未访问过的权值最小的节点int min_vertex_index = -1;for (int j = 0; j < graph->num_vertices; j++) {if (!vertices[j].visited && (min_vertex_index == -1 || vertices[j].weight < vertices[min_vertex_index].weight)) { min_vertex_index = j;}}// 将该节点标记为已访问vertices[min_vertex_index].visited = 1;// 更新与该节点相连的未访问过的节点的权值for (int j = 0; j < graph->num_vertices; j++) {if (!vertices[j].visited && graph->vertices[min_vertex_index][j] < vertices[j].weight) {vertices[j].weight = graph->vertices[min_vertex_index][j];}}}// 输出最小生成树printf("Minimum Spanning Tree:\n");for (int i = 1; i < graph->num_vertices; i++) {printf("%d - %d (%d)\n", i, (i - 1), vertices[i].weight); }}int main() {Graph graph;init_graph(&graph, 6);add_edge(&graph, 0, 1, 6);add_edge(&graph, 0, 2, 1);add_edge(&graph, 0, 3, 5);add_edge(&graph, 1, 4, 3);add_edge(&graph, 2, 4, 5);add_edge(&graph, 2, 3, 5);add_edge(&graph, 2, 5, 4);add_edge(&graph, 3 ,5 ,2);prim(&graph);return EXIT_SUCCESS;}```代码解释- 定义了Vertex结构体，用于存储节点的权值和访问状态。
c语言prim算法
Prim算法，又称普里姆算法，是一种用于解决最小生成树问题的经典算法。
它以图论为基础，能够在一个具有权重的连通无向图中找到一棵包含所有顶点的树，且树的权重之和最小。
算法的思路相对简单。
假设有一个无向图G，其中顶点集合为V，边集合为E。
算法从一个起始节点开始，逐步扩展生成树的规模，最终得到最小生成树。
1. 初始化：
- 创建一个空的集合T，用于存放最小生成树的边。
- 随机选择一个起始节点s，并将其加入T。
2. 重复以下步骤，直到所有顶点都加入T：
- 在图G中找到一条边e，满足e的一个端点在T中，另一个端点不在T中，并且e的权重最小。
- 将边e加入T，将其另一个端点加入T。
3. 输出最小生成树。
Prim算法的核心在于选择权重最小的边，将其加入生成树。
通过不断扩展生成树的规模，直到包含所有顶点，就能得到最小生成树。
这个算法的时间复杂度为O(V^2)，其中V是顶点的数量。
在稠密图中，Prim算法的效率可能较低。
为了提高效率，可以使用最小堆等
数据结构来优化选择最小边的过程，将时间复杂度降到O(ElogV)。
Prim算法在实际应用中有着广泛的用途，如网络设计、电力传输等领域。
它能够帮助我们找到一个具有最小总成本的连接方案，从而提高资源利用效率。
Prim算法是一种解决最小生成树问题的有效算法。
通过选择权重最小的边，逐步扩展生成树的规模，最终得到一个最小总成本的树。
它的应用范围广泛，并且在实际问题中具有重要意义。
希望通过以上的介绍，能够对Prim算法有一个更深入的理解。
Prim算法和Kruskal算法Prim算法和Kruskal算法都能从连通图找出最小生成树。
区别在于Prim算法是挨个找，而Kruskal是先排序再找。
一、Prim算法：Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。
(强调的是树，树是没有回路的)。
Prim算法是这样来做的：首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。
加入之后如果产生回路则跳过这条边，选择下一个结点。
当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。
Prim算法最小生成树查找过程：注意：若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。
连通网的最小生成树不一定是惟一的，但它们的权相等。
【例】在上图(e)中，若选取的轻边是(2，4)而不是(2，1)时，则得到如图(h)所示的另一棵MST。
算法特点该算法的特点是当前形成的集合T始终是一棵树。
将T中U和TE分别看作红点和红边集，V-U看作蓝点集。
算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。
MST性质保证了此边是安全的。
T从任意的根r开始，并逐渐生长直至U=V，即T 包含了C中所有的顶点为止。
MST性质确保此时的T是G的一棵MST。
因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。
算法分析该算法的时间复杂度为O(n2)。
与图中边数无关，该算法适合于稠密图。
算法演示：/sjjg/DataStructure/DS/web/flashhtml/prim.htm二、Kruskal算法：Kruskal算法与Prim算法的不同之处在于，Kruskal在找最小生成树结点之前，需要对所有权重边做从小到大排序。
将排序好的权重边依次加入到最小生成树中，如果加入时产生回路就跳过这条边，加入下一条边。
当所有结点都加入到最小生成树中之后，就找出了最小生成树。
