用Prim算法构造最小生成树

xx学院《数据结构与算法》课程设计报告书课程设计题目 PRIM算法求最小生成树院系名称计算机科学与技术系专业（班级）姓名（学号）指导教师完成时间一、问题分析和任务定义在该部分中主要包括两个方面：问题分析和任务定义；1 问题分析本次课程设计是通过PRIM（普里姆）算法，实现通过任意给定网和起点，将该网所对应的所有生成树求解出来。

在实现该本设计功能之前，必须弄清以下三个问题：1．1 关于图、网的一些基本概念1．1．1 图图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。

通常，V（G）和E（G）分别表示图G的顶点集合和边集合。

E（G）也可以为空集。

则图G只有顶点而没有边。

1．1．2 无向图对于一个图G，若边集E（G）为无向边的集合，则称该图为无向图。

1．1．3 子图设有两个图G=（V，E）G’=（V’，）,若V’是V的子集，即V’⊆V ，且E’是E的子集，即E’⊆E，称G’是G的子图。

1．1．4 连通图若图G中任意两个顶点都连通，则称G为连通图。

1．1．5 权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。

把边上带权的图称为网。

如图1所示。

1．2 理解生成树和最小生成树之间的区别和联系1．2．1 生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：V（G’）= V（G）和E（G’）⊆E（G），若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。

1．2．2 最小生成树图的生成树不是唯一的，把具有权最小的生成树称为图G的最小生成树，即生成树中每条边上的权值之和达到最小。

如图1所示。

图1．网转化为最小生成树1．3 理解PRIM（普里姆）算法的基本思想1．3．1 PRIM算法（普里姆算法）的基本思想假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。

最⼩⽣成树---普⾥姆算法（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数组记录各点的连通分量），则将其添加到最⼩⽣成树中。

最小生成树问题例题最小生成树（Minimum Spanning Tree）是图论中的一个经典问题，它是指在一个带权无向图中找到一棵生成树，使得树上所有边的权值之和最小。

最小生成树问题在实际生活中有着广泛的应用，比如电力输送、通信网络等领域。

下面我们以一个具体的例子来说明最小生成树问题的求解过程。

假设有一个无向图，图中包含了6个节点（A、B、C、D、E、F）和9条边。

每条边都有一个权值，表示连接两个节点的成本。

我们的目标是找到一棵最小生成树。

首先，我们可以使用 Prim 算法来求解最小生成树。

Prim 算法的基本思想是从一个起始节点开始，逐步扩展生成树，直到包含所有节点为止。

具体步骤如下：1. 选择一个起始节点，将其标记为已访问。

2. 从已访问的节点中，选择一条连接到未访问节点的最短边。

3. 将这条边加入到最小生成树中，并将连接的节点标记为已访问。

4. 重复步骤2和步骤3，直到所有节点都被访问过。

根据上述算法，我们可以依次选取边 AB、CD、BC、EF、DE 来构建最小生成树。

最终的最小生成树是：A-B、C-D、B-C、E-F 和 D-E 这五条边，它们的权值之和为12。

另外一个常用的求解最小生成树问题的算法是 Kruskal 算法。

Kruskal 算法的基本思想是将图中的边按照权值从小到大进行排序，然后依次选取边，如果这条边连接的两个节点不在同一个连通分量中，就将这条边加入到最小生成树中。

具体步骤如下：1. 对图中的边按照权值进行排序。

2. 从权值最小的边开始，依次选取边。

3. 如果选取的边连接的两个节点不在同一个连通分量中，就将这条边加入到最小生成树中，并将连接的节点合并为一个连通分量。

4. 重复步骤2和步骤3，直到最小生成树中包含了所有的节点。

使用 Kruskal 算法求解上述例子，我们可以依次选取边 AB、BC、CD、DE、EF 来构建最小生成树。

最终的最小生成树是：A-B、B-C、C-D、D-E 和 E-F 这五条边，它们的权值之和也是12。

模型建立与算法构造：基于Prim算法构造最小生成树作者：李琳赵娟虎建勋来源：《科教导刊·电子版》2019年第12期摘要最小生成树有许多重要的应用。

例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。

这就需要找到带权的最小生成树。

本文通过使用Matlab软件进行编程实现了用Prim算法构造最小生成树的分析运算。

本程序可以方便地处理层次分析法下较大的运算量，解决层次分析法的效率问题，提高计算机辅助决策的时效性。

其中建立了有效的基于Prim算法的数学模型并验证了模型的合理性和科学准确性。

利用MATLAB、EXCEL、SPSS13.0 for windows等软件，实现了高效、准确的研究。

关键词模型 atlab软件算法构造中图分类号：TP312 文献标识码：A1建立结构模型1.1最小生成树相关概念连通图：任意两个结点之间都有一个路径相连。

生成树（Spannirng Tree）：连通图的一个极小的连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。

最小生成树（Minimum Spannirng Tree）：连通图的最小代价的生成树（各边的权值之和最小）。

最小生成树即对于连通的带权图（连通网）G，其生成树也是带权的。

生成树T各边的权值总和称为该树的权，记作：这里：TE表示T的边集，w（u，v）表示边（u，v）的权。

权最小的生成樹称为G的最小生成树（Minimum SpannirngTree）。

最小生成树可简记为MST。

1.2 Prim算法实现Prim算法是一种贪心算法，将全部的顶点划分为2个集合，每次总在2个集合之间中找最小的一条边，局部最优最终达到全局最优，这正是贪心的思想。

在无向加权图中，n个顶点的最小生成树有n-1条边，这些边使得n个顶点之间可达，且总的代价最小。

最⼩⽣成树（普⾥姆算法）：所谓⽣成树，就是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算法通过并查集来判断两个顶点是否属于同一个连通分量，从而避免形成环。

数据结构之最⼩⽣成树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个顶点"到"该顶点"的权值。

最小生成树Prim算法和单源最短路径Dijkstra算法问题：1. （最小生成树）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，即求最小生成树。

2. （单源最短路径）给定一个权值都为正数的无向连通图和一个源点，确定它到其它点的最短距离。

之所以将这两个问题放在一起，是因为Prim算法与Dijkstra算法的思路和程序都非常相似，都是有贪心策略。

1.解法（Prim算法）：思路：设连通网络N = { V, E }，U表示已加入到生成树的顶点集合。

在初始化阶段，任取一个顶点，用其关联边的权值作为初始的V-U顶点集合的数据。

在每一步中，先在V-U顶点集合中选择距离U中任意点“最近”的顶点v，再把v加入到U中，最后看看在新的V-U顶点集合中，是否有哪个顶点距离v比距离U中其它点更近，若有则更新V-U顶点集合中的数据。

U的元素个数为V-1，所以共要进行V-1步。

总的时间复杂度为Time =O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY若用数组作为顶点权值的数据结构，T_EXTRACT-MIN用时O(V)，T_DECREASE-KEY用时O(1)，总共用时O(V^2)若用最小堆作为顶点权值的数据结构，T_EXTRACT-MIN用时O(lgV)，T_DECREASE-KEY用时O(lgV)，总共用时O((V+E)*lgV)若用斐波那契堆作为顶点权值的数据结构，T_EXTRACT-MIN平均用时O(lgV)，T_DECREASE-KEY平均用时O(1)，总共用时O(E+V*lgV)下面的代码使用数组作为顶点权值的数据结构：[cpp]view plaincopy1.#include <iostream>2.#include <algorithm>ing namespace std;4.5.#define MAXN 10016.#define INF 10000007.8.int lowcost[MAXN]; // 距离U中顶点的最小权值9.bool visited[MAXN]; // 若为true表示已加入到集合U中10.int mst[MAXN]; // 距离U中哪个顶点最短11.int graph[MAXN][MAXN]; // 用矩阵表示图上各边权值12.13.void Prim(int n)14.{15.int i, j;16. memset(visited, 0, n*sizeof(bool));17. visited[0] = true;18. mst[0] = -1;19.for (i=1; i<n; i++)20. {21. lowcost[i] = graph[0][i];22. mst[i] = 0;23. }24.for (i=1; i<=n-1; i++)25. {26.// 取V-U中的最小权值T_EXTRACT-MIN O(V)27.int min=INF, minid;28.for (j=1; j<n; j++)29.// 用visited数组确定V-U30.if (!visited[j] && lowcost[j] < min)31. {32. min = lowcost[j];33. minid = j;34. }35. visited[minid] = true;36.// 减小V-U中的权值T_DECREASE-KEY O(1)37.for (j=1; j<n; j++)38.if (!visited[j] && lowcost[j] > graph[minid][j])39. {40. lowcost[j] = graph[minid][j];41. mst[j] = minid;42. }43. }44.}45.46.int main()47.{48.int n, m, i, j;49. cin >> n >> m;50.for (i=0; i<n; i++)51.for (j=0; j<n; j++)52. graph[i][j] = INF;53.for (i=0; i<m; i++)54. {55.char a[3], b[3];56.int c;57. scanf("%s %s %d",&a, &b, &c);58. graph[a[0]-'A'][b[0]-'A'] = c;59. graph[b[0]-'A'][a[0]-'A'] = c;60. }61. Prim(n);62.int total = 0;63.for (i=1; i<n; i++)64. {65. total += lowcost[i];66. printf("%c-%c: %d\n", i+'A', mst[i]+'A', lowcost[i]);67. }68. printf("%d\n", total);69.}2.解法（Dijkstra算法）：思路：设连通网络N = { V, E }和给定源点u，U表示已确定最短路径的顶点集合。