用邻接矩阵存储无向图，实现最小生成树Prim算法，图中边的权值为整型，顶点个数少于 10 个用c语言

在C语言中，使用邻接矩阵（Adjacency Matrix）来表示无向图是一种常见的方法，其中矩阵的行和列分别代表图中的顶点，矩阵中的每个元素表示两个顶点之间是否存在边以及边的权重。对于Prim算法（Prim-Kruskal的变种），它的目标是在给定的无向图中找到连接所有顶点的最小生成树。 下面是一个简单的C语言实现Prim算法的示例，假设我们有8个顶点和整型的边权值： ```c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define V 8 // 顶点数量 // 邻接矩阵存储无向图 int graph[V][V] = { {0, 2, 0, 6, 0, 0, 2, 0}, {2, 0, 3, 8, 5, 0, 0, 4}, {0, 3, 0, 0, 7, 9, 0, 1}, {6, 8, 0, 0, 9, 0, 7, 0}, {0, 5, 7, 9, 0, 1, 0, 6}, {0, 0, 9, 0, 1, 0, 4, 5}, {2, 0, 0, 7, 0, 4, 0, 9}, {0, 4, 1, 0, 6, 5, 9, 0} }; // 记录已选取的边 bool mst_set[V]; // 边的比较函数 bool compare(int u, int v) { return graph[u][v] < graph[v][u]; } // Prim算法实现 void primMST() { // 初始化mst_set和最小生成树的总成本 for (int i = 0; i < V; i++) { mst_set[i] = false; min_cost = INT_MAX; } // 选择任意一个顶点作为起始点 int start = 0; printf("Selected vertex: %d\n", start); mst_set[start] = true; // 添加起点到其他所有顶点的边 for (int i = 0; i < V; i++) if (!mst_set[i] && graph[start][i] != 0) min_cost = graph[start][i], edge[start][i] = start; while (true) { // 找到当前图中距离起点最近的未加入的顶点 int u = -1, min_edge = INT_MAX; for (int v = 0; v < V; v++) { if (!mst_set[v] && graph[edge[u][v]][v] < min_edge) u = v, min_edge = graph[edge[u][v]][v]; } if (u == -1) break; // 如果找不到这样的顶点，说明已经构建了最小生成树 // 将找到的顶点加入到最小生成树，并更新其相邻节点的距离 mst_set[u] = true; printf("Adding edge from vertex %d to vertex %d with cost %d\n", edge[u][u], u, min_edge); for (int v = 0; v < V; v++) if (!mst_set[v] && graph[u][v] != 0 && graph[u][v] + min_edge < graph[edge[u][v]][v]) graph[edge[u][v]][v] = graph[u][v] + min_edge, edge[u][v] = u; } } // 主函数 int main() { primMST(); // 输出最小生成树的边及其权值 printf("\nMinimum Spanning Tree:\n"); for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (graph[i][j] != 0 && !mst_set[j]) { printf("Edge from %d to %d with weight: %d\n", i, j, graph[i][j]); } } } return 0; } ``` 这个例子只是一个基础版本，实际应用中你可能需要添加更多的错误检查和优化。在运行过程中，它会按照Prim算法寻找并添加最小生成树的边，直到覆盖所有顶点。