下载文档原格式
c++ prim函数
C++的STL库中有一个非常重要的函数——prim函数。
prim函数是一种用于求解最小生成树问题的算法，可以在图中找到一棵包含全部节点的最小权值树。
prim函数的基本思想是从任意一个节点开始，不断添加与已有节点相连的权值最小的节点，直到所有节点都被加入为止。
具体实现过程如下：
1. 初始化一个集合S，包含任意一个节点v。
2. 初始化一个set，用于保存所有与集合S相连的节点和相应的边权值，根据边权值从小到大排序。
3. 从set中取出权值最小的边(u,w)，如果u不在集合S中，则将u加入集合S，并将(u,w)加入最小生成树的边集中。
4. 将所有与u相连的节点v及其边权值添加到set中，如果v 已经在S中，则从set中删除。
5. 重复步骤3和4，直到集合S包含所有节点为止。
prim函数的时间复杂度为O(ElogV)，其中E表示边数，V表示节点数。
它是一种贪心算法，每次选择当前情况下的最优解，但并不保证一定能够得到全局最优解。
- 1 -。
C语⾔实现最⼩⽣成树构造算法最⼩⽣成树最⼩⽣成树（minimum spanning tree）是由n个顶点，n-1条边，将⼀个连通图连接起来，且使权值最⼩的结构。
最⼩⽣成树可以⽤Prim（普⾥姆）算法或kruskal（克鲁斯卡尔）算法求出。
我们将以下⾯的带权连通图为例讲解这两种算法的实现：注：由于测试输⼊数据较多，程序可以采⽤⽂件输⼊Prim（普⾥姆）算法时间复杂度：O（N^2）（N为顶点数）prim算法⼜称“加点法”，⽤于边数较多的带权⽆向连通图⽅法：每次找与之连线权值最⼩的顶点，将该点加⼊最⼩⽣成树集合中注意：相同权值任选其中⼀个即可，但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最⼩⽣成树：1.初始化：lowcost[i]:表⽰以i为终点的边的最⼩权值,当lowcost[i]=0表⽰i点加⼊了MST。
mst[i]:表⽰对应lowcost[i]的起点，当mst[i]=0表⽰起点i加⼊MST。
由于我们规定最开始的顶点是1，所以lowcost[1]=0，MST[1]=0。
即只需要对2~n进⾏初始化即可。
#define MAX 100#define MAXCOST 0x7fffffffint graph[MAX][MAX];void prim(int graph[][MAX], int n){int lowcost[MAX];int mst[MAX];int i, j, min, minid, sum = 0;for (i = 2; i <= n; i++){lowcost[i] = graph[1][i];//lowcost存放顶点1可达点的路径长度mst[i] = 1;//初始化以1位起始点}mst[1] = 0;2.查找最⼩权值及路径更新定义⼀个最⼩权值min和⼀个最⼩顶点ID minid，通过循环查找出min和minid，另外由于规定了某⼀顶点如果被连⼊，则lowcost[i]=0，所以不需要担⼼重复点问题。
求出下图的最小生成树解：MATLAB程序：% 求图的最小生成树的prim算法。
% result的第一、二、三行分别表示生成树边的起点、终点、权集合% p——记录生成树的的顶点，tb=V\pclc;clear;% a(1,2)=50; a(1,3)=60;% a(2,4)=65; a(2,5)=40;% a(3,4)=52;a(3,7)=45;% a(4,5)=50; a(4,6)=30;a(4,7)=42;% a(5,6)=70;% a=[a;zeros(2,7)];e=[1 2 20;1 4 7;2 3 18;2 13 8;3 5 14;3 14 14;4 7 10;5 6 30;5 9 25;5 10 9;6 10 30;6 11 30;7 8 2;7 13 5;8 9 4;8 14 2;9 10 6;9 14 3;10 11 11;11 12 30];n=max([e(:,1);e(:,2)]); % 顶点数m=size(e,1); % 边数M=sum(e(:,3)); % 代表无穷大a=zeros(n,n);for k=1:ma(e(k,1),e(k,2))=e(k,3);enda=a+a';a(find(a==0))=M; % 形成图的邻接矩阵result=[];p=1; % 设置生成树的起始顶点tb=2:length(a); % 设置生成树以外顶点while length(result)~=length(a)-1 % 边数不足顶点数-1temp=a(p,tb);temp=temp(:); % 取出与p关联的所有边d=min(temp); % 取上述边中的最小边[jb,kb]=find(a(p,tb)==d); % 寻找最小边的两个端点(可能不止一个)j=p(jb(1));k=tb(kb(1)); % 确定最小边的两个端点result=[result,[j;k;d]]; % 记录最小生成树的新边p=[p,k]; % 扩展生成树的顶点tb(find(tb==k))=[]; % 缩减生成树以外顶点endresult % 显示生成树（点、点、边长）weight=sum(result(3,:)) % 计算生成树的权程序结果：result =1 4 7 8 14 7 9 13 10 10 14 10 11 4 7 8 14 9 13 102 5 113 6 12 7 10 2 2 3 5 6 8 9 11 14 30 30 weight =137附图最小生成树的权是137。
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的初值均为空集。
c语言prim算法摘要：1.C 语言和Prim 算法简介2.Prim 算法的应用3.Prim 算法的实现4.结论正文：一、C 语言和Prim 算法简介C 语言是一种广泛应用的计算机编程语言，以其高效性和灵活性著称。
它被广泛应用于操作系统、嵌入式系统、游戏开发等领域。
Prim 算法是一种用于解决无向图最小生成树问题的贪心算法。
它的基本思想是从一个顶点开始，不断地寻找与当前生成树距离最近的顶点，将其加入到生成树中，直到所有顶点都加入到生成树中为止。
二、Prim 算法的应用Prim 算法在图论中有着广泛的应用，例如在网络设计、最短路径问题、数据压缩等领域。
在网络设计中，可以用Prim 算法来找到一个网络的最小生成树，从而减少网络的成本。
在最短路径问题中，Prim 算法可以用来找到一个图中两点之间的最短路径。
在数据压缩中，Prim 算法可以用来找到一个图的最小生成树，从而将图压缩成一个更小的表示。
三、Prim 算法的实现下面是一个简单的C 语言实现的Prim 算法：```c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>typedef struct node {int vertex;int weight;} node;typedef struct graph {int vertices;node **adjList;} graph;void add_edge(graph *g, int src, int dest, int weight) { g->adjList[src] = (node*) malloc(sizeof(node));g->adjList[src]->vertex = dest;g->adjList[src]->weight = weight;g->adjList[dest] = (node*) malloc(sizeof(node));g->adjList[dest]->vertex = src;g->adjList[dest]->weight = weight;}bool is_valid_edge(graph *g, int src, int dest) {return g->adjList[src]!= NULL && g->adjList[dest]!= NULL; }int prim_min_tree_weight(graph *g) {int sum = 0;int *dist = (int*) calloc(g->vertices, sizeof(int));for (int i = 0; i < g->vertices; i++) {dist[i] = INT_MAX;}int min_weight = INT_MAX;int root = -1;while (root == -1) {for (int i = 0; i < g->vertices; i++) {if (dist[i] == INT_MAX) {continue;}for (int j = 0; j < g->vertices; j++) {if (is_valid_edge(g, i, j) && dist[j] > dist[i] + g->adjList[i]->weight) {dist[j] = dist[i] + g->adjList[i]->weight;if (min_weight > dist[j]) {min_weight = dist[j];root = j;}}}}}for (int i = 0; i < g->vertices; i++) { sum += dist[i];}free(dist);return min_weight;}int main() {graph g = {3, NULL};add_edge(&g, 0, 1, 4);add_edge(&g, 0, 2, 3);add_edge(&g, 1, 2, 1);add_edge(&g, 1, 3, 2);add_edge(&g, 2, 3, 4);printf("Minimum tree weight: %d ", prim_min_tree_weight(&g));return 0;}```四、结论C 语言和Prim 算法的结合可以有效地解决图论中的最小生成树问题。
PAT 数据结构 06-图6. 公路村村通（30）Prim最小生成树算法现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式说明：输入数据包括城镇数目正整数N（<=1000）和候选道路数目M（<=3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。
为简单起见，城镇从1到N编号。
输出格式说明：输出村村通需要的最低成本。
如果输入数据不足以保证畅通，则输出-1，表示需要建设更多公路。
样例输入与输出：用Prim最小生成树算法来写：已吸收的结点为集合AB，一开始只有1号结点。
未吸收的结点为集合UD，一开始包含除1号外的所有结点。
每次以最小边的代价将UD中的一个结点吸收到AB。
一开始想到可以用穷举的方法写，当AB集合有k个结点时，UD集合有N-K 个，穷举两个集合的所有可能连线，通常来说遍历的效率较低，说得形象点，k 每次变化时，每次都要判断1号结点都要与UD集合中的所有结点是否有边，显然第一次之后的判断都是多余的。
从这个角度来想，我们每次只要判断AB中最新的一个结点与UD中所有结点是否有边即可。
为了便于操作，定义结点结构体如下面代码所示。
由于我是第一次写该算法，多加了前驱结点proNode，用于输出具体的生成树。
该变量在本题中是多余的，可以去掉。
[cpp]view plain copy print?1./*2015.7.16cyq*/2.//Prim最小生成树算法3.#include<iostream>4.#include<vector>5.#include<fstream>6.#include<algorithm>7.std;8.9.int MAX=2147483647;10.//ifstream fin("case1.txt");11.//#define cin fin12.13.node{14.int num;//结点序号15.int weight;//能连通到已确定子图的最小边16.int preNode;//最小边依附的结点,用于输出具体生成树17.node():num(-1),weight(-1),preNode(-1){}18.node(int n,int wei,int preN):num(n),weight(wei),preNode(preN){}19.bool operator<(node&a){20.weight<a.weight;21.}22.};23.24.int main(){25.int N,M;26.cin>>N>>M;27.vector<vector<int>>edges(N+1,vector<int>(N+1,-1));//-1表示不连通28.int a,b,c;29.(M--){30.cin>>a>>b>>c;31.edges[a][b]=c;32.edges[b][a]=c;33.}34.35.vector<node>AB;//已吸收的点,一开始只有结点136.AB.push_back(node(1,0,-1));//37.vector<node>UD(N-1);//未吸收的点38.(int i=0;i<N-1;i++){39.UD[i].num=i+2;//编号2到N40.int tmp=edges[1][UD[i].num];41.(tmp>0){//能连到结点1的结点42.UD[i].weight=tmp;43.UD[i].preNode=1;44.}{//不能连到结点1的结点45.UD[i].weight=MAX;46.UD[i].preNode=-1;47.}48.}49.int totalLength=0;50.//vector<pair<int,int>>result;//用于输出具体生成树51.(!UD.empty()){52.sort(UD.begin(),UD.end());53.node cur=UD[0];//取出能以最小代价吸收的点54.UD.erase(UD.begin());55.(cur.weight==MAX){56.cout<<"-1"<<endl;57.0;58.}59.totalLength+=cur.weight;60.//result.push_back(make_pair(cur.num,cur.preNode));61.(auto it=UD.begin();it!=UD.end();++it){//用该点修正未吸收的点62.int w=edges[cur.num][(*it).num];63.(w>0){64.(w<(*it).weight){65.(*it).weight=w;66.(*it).preNode=cur.num;67.}68.}69.}70.}71.cout<<totalLength<<endl;72.//for(auto it=result.begin();it!=result.end();++it){//输出最小生成树73.//cout<<(*it).first<<""<<(*it).second<<""<<edges[(*it).first][(*it).second]<<endl;74.//}75.0;76.}事实上，可以进一步把UD集合分成两个集合，第一个集合中的点与AB相邻，第二个集合的点与AB不相邻，尚未探测到。
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"s 算法) 是一种用于寻找最小生成树的算法。
它的时间复杂度为 $O(Elog E)$,其中 $E$ 是边数。
下面是 C++ 普姆算法的实现:```cpp#include <iostream>#include <vector>#include <cmath>using namespace std;// 定义边数const int E = 100010;// 定义最小生成树边权数组vector<int> adj[E];int weight[E];// 普姆算法int Prim(int u, vector<bool> &visited) {// 如果当前节点已经被访问过，则直接返回当前节点的值if (visited[u]) {return u;}// 计算当前节点到其他节点的最短路for (int v : adj[u]) {if (!visited[v]) {// 将当前节点添加到最小生成树中weight[u] += weight[v];adj[u].push_back(v);}}// 如果当前节点到其他节点的最短路长度小于当前的权值，则将当前节点的权值更新为最短路长度for (int v : adj[u]) {if (!visited[v]) {int dist = sqrt(pow(weight[u], 2) + pow(weight[v], 2)); weight[u] = dist;}}// 返回当前节点的值return u;}// 计算最小生成树vector<int> PrimTree(vector<int> &adj, int u) {// 如果当前节点已经被访问过，则直接返回当前节点的值vector<int> tree(adj.size(), -1);tree[u] = 0;// 辅助数组，记录每个节点到其他节点的最短路vector<int> pd(adj.size(), -1);for (int v : adj[u]) {if (!pd[v]) {pd[v] = u;}}// 循环遍历每个节点，并将当前节点添加到最小生成树中 for (int v = 0; v < adj.size(); v++) {int pdv = pd[v];if (pdv != -1 && weight[v] < weight[pdv]) {tree[v] = pdv;}}return tree;}int main() {// 读入边数cin >> E;// 读入边权数组for (int i = 0; i < E; i++) {cin >> weight[i];}// 初始化邻接表for (int i = 0; i < E; i++) {for (int j = 0; j < E; j++) {if (weight[i] < weight[j]) {adj[i].push_back(j);}}}// 计算最小生成树vector<int> tree = PrimTree(adj, 0);// 输出最小生成树for (int i = 0; i < tree.size(); i++) {cout << tree[i] << " ";}cout << endl;return 0;}```在上述代码中，我们首先定义了边数 `E`,然后读入边权数组`weight`。
最⼩⽣成树（普⾥姆算法）：所谓⽣成树，就是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例题解释。
c语言prim算法Prim算法是一种用于求解最小生成树问题的算法，它通过逐步选择与当前生成树相邻且权重最小的边来逐步构建最小生成树。
下面是使用C语言实现Prim算法的示例代码：```c#include <stdio.h>#include <limits.h>#define V 5 // 图中顶点的数量int minKey(int key[], int mstSet[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++) {if (mstSet[v] == 0 && key[v] < min) {min = key[v];min_index = v;}}return min_index;}void printMST(int parent[], int graph[V][V]) {printf("Edge \tWeight\n");for (int i = 1; i < V; i++) {printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]); }}void primMST(int graph[V][V]) {int parent[V]; // 存放最小生成树的边int key[V]; // 存放顶点的键值int mstSet[V]; // 标记顶点是否已包含在最小生成树中for (int i = 0; i < V; i++) {key[i] = INT_MAX;mstSet[i] = 0;}key[0] = 0;parent[0] = -1;for (int count = 0; count < V - 1; count++) {int u = minKey(key, mstSet);mstSet[u] = 1;for (int v = 0; v < V; v++) {if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}printMST(parent, graph);}int main() {int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph);return 0;}```此示例实现了Prim算法来求解给定图形的最小生成树，并且在控制台打印出了所得到的最小生成树的边及其权重。
