普里姆算法c语言实现

以下是普里姆算法（Prim's Algorithm）的C语言实现：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <stdbool.h>
5. #define INF 99999 // 无穷大，表示不可达
7. int n; // 顶点数
8. int m; // 边数
9. int graph[10][10]; // 邻接矩阵表示的图
11. int prim() {
12. ????int parent[10]; // 存储构造的MST中每个顶点的父节点
13. ????int key[10]; // 存储每个顶点到MST的距离（权值）
14. ????bool visited[10] = {false}; // 标记每个顶点是否已经被访问过
15. ????for (int i = 0; i < n; i++) {
16. ????????key[i] = INF; // 初始化所有顶点到MST的距离为无穷大
17. ????}
18. ????key[0] = 0; // 让第一个顶点作为MST的第一个顶点
19. ????parent[0] = -1; // 第一个顶点是MST的第一个顶点
20. ????for (int i = 0; i < n - 1; i++) {
21. ????????// 从未被访问过的顶点中选择一个距离最小的顶点v
22. ????????int min_key = INF;
23. ????????int min_index = -1;
24. ????????for (int j = 0; j < n; j++) {
25. ????????????if (!visited[j] && key[j] < min_key) {
26. ????????????????min_key = key[j];
27. ????????????????min_index = j;
28. ????????????}
29. ????????}
30. ????????visited[min_index] = true; // 将选中的顶点v标记为已访问过
31. ????????// 更新与v相邻的顶点到MST的距离
32. ????????for (int j = 0; j < n; j++) {
33. ????????????if (graph[min_index][j] != 0 && !visited[j] && graph[min_index][j] < key[j]) {
34. ????????????????parent[j] = min_index; // 将j的父节点设为min_index，即v
35. ????????????????key[j] = graph[min_index][j]; // 更新key[j]，即更新j到MST的距离
36. ????????????}
37. ????????}
38. ????}
39. ????// 输出构造的MST中每个顶点的权值和所在MST中的父节点
40. ????printf("Edge \tWeight\n");
41. ????for (int i = 1; i < n; i++) {
42. ????????printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
43. ????}
44. ????return 0;
45. }
47. int main() {
48. ????printf("Enter the number of vertices and edges: ");
49. ????scanf("%d %d", &n, &m);
50. ????printf("Enter the adjacency matrix of the graph:\n");
51. ????for (int i = 0; i < m; i++) {
52. ????????for (int j = 0; j < n; j++) {
53. ????????????scanf("%d", &graph[i][j]);
54. ????????}
55. ????}
56. ????prim(); // 调用Prim函数求解MST并输出结果
57. ????return 0;
58. }

这段代码实现了普里姆算法（Prim's Algorithm）来寻找给定图的最小生成树（Minimum Spanning Tree，MST）。下面是该代码的流程解释：

1. 输入顶点数n和边数m。
2. 输入邻接矩阵表示的图，邻接矩阵是一个n×n的二维数组，其中graph[i][j]表示顶点i和顶点j之间的边的权值，0表示两个顶点之间没有边。
3. 定义一个数组parent，用于存储构造的MST中每个顶点的父节点。初始时，除了第一个顶点（起点）外，其他所有顶点的父节点均设置为-1。
4. 定义一个数组key，用于存储每个顶点到MST的距离（权值）。初始化时，将所有顶点到MST的距离设置为无穷大，除了起点到MST的距离设置为0。
5. 定义一个数组visited，用于标记每个顶点是否已经被访问过。初始时，所有顶点均未被访问过。
6. 在while循环中，从未被访问过的顶点中选择一个距离最小的顶点v。从这些未被访问的顶点中选择一个距离最小的顶点可以通过遍历所有未被访问的顶点并更新它们的距离来实现。
7. 将选中的顶点v标记为已访问过，并更新与v相邻的顶点到MST的距离。如果某个相邻顶点的距离小于当前该顶点到MST的距离，则更新该顶点到MST的距离，并将该顶点的父节点设置为v。
8. 重复上述步骤，直到所有顶点都被访问过或者MST中已经包含了n-1条边。
9. 输出构造的MST中每个顶点的权值和所在MST中的父节点。可以通过遍历所有顶点并输出它们的父节点和权值来实现。

这段代码使用邻接矩阵来表示图，是一种较为直观的方式。但是，在实际应用中，为了减少内存占用和提高运行效率，通常会使用邻接表等其他数据结构来表示图。