prim算法代码实现

### Prim算法代码实现示例 #### 使用C语言实现Prim算法 下面展示了一个基于邻接矩阵的Prim算法C语言实现： ```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] && 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] && graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v]; } printMST(parent, graph); } ``` 这段程序展示了如何通过邻接矩阵来构建最小生成树(Minimum Spanning Tree)，并最终输出构成此树的各条边及其对应的权重[^1]。 #### 使用C++实现Prim算法 对于更现代的语言特性支持，这里给出一段采用优先队列优化后的C++版本Prim算法实现方式： ```cpp #include<bits/stdc++.h> using namespace std; typedef pair<int,int> ii; const int MAXN=1e4+7; vector<ii> adj[MAXN]; bool vis[MAXN]={false}; priority_queue<ii,vector<ii>,greater<ii>> pq; void addEdge(int u,int v,int w){ adj[u].emplace_back(v,w); adj[v].emplace_back(u,w); } void primsAlgo(int src,int n){ vector<int> key(n,INT_MAX),par(n,-1); pq.push({key[src]=0,src}); while(!pq.empty()){ auto [w,u]=pq.top(); pq.pop(); if(vis[u]) continue; vis[u]=true; for(auto& [v,weight]:adj[u]){ if(!vis[v]&&weight<key[v]){ par[v]=u; key[v]=weight; pq.emplace(weight,v); } } } cout<<"Edge\tWeight\n"; for(int i=1;i<n;++i) cout<<par[i]<<"--"<<i<<"\t"<<key[i]<<endl; } ``` 上述代码利用了`std::pair`, `std::vector` 和 `std::priority_queue` 来简化操作流程，在处理大规模稀疏图时效率更高。同时提供了更加直观的方式去理解和应用Prim算法[^2]。 #### MATLAB内置Prim算法 MATLAB也提供了一种简洁的方式来调用其内部封装好的Prim函数来进行最小生成树求解: ```matlab % 创建无向加权图对象G s = [1 2 2 3 4 4 5 6 8]; t = [2 3 4 5 5 6 6 7 9]; weights = randi([1, 10], 1, length(s)); G = graph(s,t,weights); % 调用prim方法获取最小生成树T T = prim(G,'CostOutput','on'); % 显示结果 disp('Minimum spanning tree:'); figure(1); clf; plot(T,'Layout','force'); title('Minimum Spanning Tree using PRIM algorithm') ``` 这段脚本创建了一个随机赋予权重的无向图，并使用Matlab自带的功能快速得到最小生成树的结果可视化图像[^3]。