首页用c语言代码写邻接矩阵存储的无向图，用prim算法构造最小生成树的代码

用c语言代码写邻接矩阵存储的无向图，用prim算法构造最小生成树的代码

时间: 2024-12-29 15:32:33 浏览: 72

在C语言中，我们可以使用邻接矩阵来表示无向图，并利用Prim算法（也叫普里姆算法）找到连接图中所有顶点的最小生成树。下面是一个简单的示例，我们将使用数组和嵌套循环来实现邻接矩阵和Prim算法： ```c #include <stdio.h> #define V 5 // 图中的顶点数 // 邻接矩阵结构体 typedef struct { int graph[V][V]; // 用于存储图的邻接矩阵 } Graph; // 判断是否已经访问过某个顶点 int visited[V]; int minDistance(int dist[], int s) { int min = INT_MAX; int min_index = -1; for (int v = 0; v < V; v++) if (dist[v] <= min && !visited[v]) min = dist[v], min_index = v; return min_index; } // Prim's algorithm void primMST(Graph* g, int src) { // 初始化距离数组和访问数组 int dist[V] = {INT_MAX}; dist[src] = 0; while (!isFull()) { int u = minDistance(dist, src); printf("Adding edge %d to MST\n", u); // 更新邻接矩阵中从u到未访问节点的最短路径 for (int v = 0; v < V; v++) { if (g->graph[u][v] != 0 && dist[u] + g->graph[u][v] < dist[v]) { dist[v] = dist[u] + g->graph[u][v]; } } visited[u] = 1; // 标记已访问 } } // 主函数 int main() { Graph g; int edges[V][V]; // 假设我们已经有了边的权重 // 初始化邻接矩阵 for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { g.graph[i][j] = edges[i][j]; // 填充实际的边权重 } } primMST(&g, 0); // 使用源节点0开始 return 0; } ``` 请注意，这个例子假设了边的权重已经存在`edges`数组中。实际应用中，你需要先定义好图的结构并填充合适的边权重。

阅读全文