最小生成树 繁忙的都市C语言实现

最小生成树是一种图论算法，用于在一个加权连通无向图中找到一棵边权总和最小子的树。常见的最小生成树算法有Prim算法和Kruskal算法。

在C语言中实现最小生成树，我们可以选择Prim算法，它从一个初始顶点开始，逐步添加与当前树相连且权重最低的边，直到所有顶点都被包含。以下是简化版的Prim算法实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define V 6 // 假设城市数量

typedef struct {
    int src;   // 源节点
    int weight; // 边的权重
} Edge;

// 边的比较函数
bool compareEdge(Edge e1, Edge e2) {
    return e1.weight < e2.weight;
}

// Prim's algorithm
void primMST(int graph[V][V], int n) {
    bool marked[V] = {false}; // 标记数组，标记已加入树的节点
    Edge minHeap[] = {graph[0][1], graph[0][2], ...}; // 初始化最小堆
    int key[V]; // 存储每个节点到已连接树的最小权重

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX; // 初始化为无穷大
        if (!marked[0]) {
            key[0] = graph[0][0];
            marked[0] = true;
        }
        for (int j = 1; j < n; j++) {
            if (!marked[j] && graph[0][j] < key[j]) {
                key[j] = graph[0][j];
            }
        }
    }

    for (int count = 1; count < n; count++) {
        int u = -1; // 当前未加入树的最小节点
        for (int v = 1; v < n; v++) {
            if (!marked[v] && (u == -1 || key[u] > key[v])) {
                u = v;
            }
        }
        marked[u] = true;
        printf("Adding edge between vertex %d and %d\n", 0, u);

        // 更新其他未加入树的节点到新节点的路径
        for (int i = 1; i < n; i++) {
            if (!marked[i] && graph[u][i] && graph[u][i] < key[i]) {
                key[i] = graph[u][i];
            }
        }
    }
}

int main() {
    int graph[V][V] = {/* 图的邻接矩阵 */};
    primMST(graph, V);
    return 0;
}