Prim算法用于求解无向加权图的最小生成树，从一个顶点出发，每次选择权重最小的边扩展生成树。使用邻接矩阵适合稠密图，通过lowcost数组和visited数组维护最短距离与访问状态；邻接表结合优先队列适合稀疏图，利用最小堆高效选取最小边。代码实现需初始化起点，循环更新未访问顶点的最短距离，最终累加总权重。注意判断图的连通性，避免不连通情况下的错误结果。
Prim算法用于求解无向加权图的最小生成树（MST），核心思想是从一个起始顶点出发，每次选择与当前生成树相连且权重最小的边，逐步扩展直到包含所有顶点。C++中可以通过邻接矩阵或邻接表结合优先队列来高效实现。
使用邻接矩阵和数组实现（适合稠密图）
当图的边较多时，使用邻接矩阵存储更直观。通过维护一个lowcost数组记录各顶点到当前生成树的最短距离，以及一个visited数组标记是否已加入生成树。
关键步骤：
- 初始化：从顶点0开始，lowcost[i] = graph[0][i]
- 循环n-1次，每次找出lowcost中最小且未访问的顶点u
- 将u加入生成树，累加该边权值
- 用u更新其他顶点到生成树的最短距离
使用邻接表和优先队列（适合稀疏图）
对于边数较少的图，邻接表+优先队列（最小堆）效率更高。C++中可用priority_queue实现堆结构，自动维护最小边。
立即学习“C++免费学习笔记（深入）”；
MD5校验和计算小程序（C）
下载
C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。
实现要点：
- 定义边结构体：包含目标顶点和权重
- 使用vector
air >>存储邻接表 - 优先队列保存{weight, vertex}，按权重从小到大排序
- 从任意起点开始，将相邻边加入队列
- 取出最小边，若终点未访问，则加入生成树并扩展新边
代码示例（邻接矩阵版）
以下是一个基于邻接矩阵的Prim算法实现，假设图是连通的：
#include#include using namespace std; const int MAXN = 100; int graph[MAXN][MAXN]; bool visited[MAXN]; int lowcost[MAXN]; int prim(int n) { fill(lowcost, lowcost + n, INT_MAX); fill(visited, visited + n, false); lowcost[0] = 0; int totalWeight = 0; for (int i = 0; i < n; i++) { int u = -1, minVal = INT_MAX; for (int j = 0; j < n; j++) { if (!visited[j] && lowcost[j] < minVal) { minVal = lowcost[j]; u = j; } } if (u == -1) break; visited[u] = true; totalWeight += lowcost[u]; for (int v = 0; v < n; v++) { if (!visited[v] && graph[u][v] > 0 && graph[u][v] < lowcost[v]) { lowcost[v] = graph[u][v]; } } } return totalWeight; }
注意事项与优化建议
实际应用中需注意图的连通性判断，若最终访问顶点数少于n，说明图不连通，无法构成生成树。对于大规模稀疏图，推荐使用邻接表配合优先队列，时间复杂度可降至O(E log V)。手动实现堆或使用set也可进一步优化性能。
基本上就这些，根据数据规模选择合适的数据结构即可。
