C语言实现最经济的网络建设方案：最小生成树算法

本代码使用C语言实现了在n个城市（n>=5）之间建设网络的最经济方案，并保证网络连通。代码实现了以下功能：

手动录入城市数n（n>=5）及各城市之间的距离并将其储存起来。
存储结构采用邻接表和邻接矩阵两种。
代码编写时需要采用普利姆算法和克鲁斯卡尔算法两种。
输出所得的邻接表或邻接矩阵。
输出所得的最小生成树，最小生成树需要包括节点及权值。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_CITY 100 // 最大城市数量

// 邻接表中的节点
typedef struct Node {
    int dest; // 目标城市
    int weight; // 距离
    struct Node* next; // 下一个节点
} Node;

// 邻接表
typedef struct Graph {
    int numVertices; // 城市数量
    Node** adjLists; // 邻接表数组
} Graph;

// 创建节点
Node* createNode(int dest, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->adjLists = (Node**)malloc(numVertices * sizeof(Node*));

    int i;
    for (i = 0; i < numVertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
    // 添加从src到dest的边
    Node* newNode = createNode(dest, weight);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 添加从dest到src的边
    newNode = createNode(src, weight);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 输出邻接表
void printGraph(Graph* graph) {
    int v;
    for (v = 0; v < graph->numVertices; v++) {
        Node* temp = graph->adjLists[v];
        printf('顶点 %d 的邻接表：\n', v);
        while (temp) {
            printf('-> %d(%d) ', temp->dest, temp->weight);
            temp = temp->next;
        }
        printf('\n');
    }
}

// 普利姆算法
void primMST(Graph* graph) {
    int parent[MAX_CITY]; // 最小生成树的父节点
    int key[MAX_CITY]; // 顶点的键值
    bool mstSet[MAX_CITY]; // 顶点是否已包含在最小生成树中

    int i;
    for (i = 0; i < graph->numVertices; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    int count;
    for (count = 0; count < graph->numVertices - 1; count++) {
        int u;
        int minKey = INT_MAX;
        for (i = 0; i < graph->numVertices; i++) {
            if (!mstSet[i] && key[i] < minKey) {
                minKey = key[i];
                u = i;
            }
        }

        mstSet[u] = true;

        Node* temp = graph->adjLists[u];
        while (temp) {
            int v = temp->dest;
            int weight = temp->weight;
            if (!mstSet[v] && weight < key[v]) {
                parent[v] = u;
                key[v] = weight;
            }
            temp = temp->next;
        }
    }

    printf('最小生成树：\n');
    for (i = 1; i < graph->numVertices; i++) {
        printf('%d - %d\n', parent[i], i);
    }
}

// 克鲁斯卡尔算法

// 并查集的节点
typedef struct Subset {
    int parent; // 父节点
    int rank; // 秩
} Subset;

// 查找根节点（路径压缩）
int find(Subset subsets[], int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

// 合并两个集合（按秩合并）
void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// 比较两个边的权值
int compare(const void* a, const void* b) {
    return ((Node*)a)->weight - ((Node*)b)->weight;
}

// 克鲁斯卡尔算法生成最小生成树
void kruskalMST(Graph* graph) {
    Node* result[MAX_CITY];
    int e = 0; // 最小生成树中边的数量

    int i;
    Node* edges[graph->numVertices * graph->numVertices];
    for (i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjLists[i];
        while (temp) {
            edges[e++] = temp;
            temp = temp->next;
        }
    }

    qsort(edges, e, sizeof(Node*), compare);

    Subset* subsets = (Subset*)malloc(graph->numVertices * sizeof(Subset));
    for (i = 0; i < graph->numVertices; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }

    i = 0;
    int count = 0;
    while (count < graph->numVertices - 1) {
        Node* nextEdge = edges[i++];
        int x = find(subsets, nextEdge->dest);
        int y = find(subsets, nextEdge->weight);

        if (x != y) {
            result[count++] = nextEdge;
            Union(subsets, x, y);
        }
    }

    printf('最小生成树：\n');
    for (i = 0; i < count; i++) {
        printf('%d - %d\n', result[i]->dest, result[i]->weight);
    }
}

int main() {
    int n; // 城市数量
    printf('请输入城市数量（至少为5）：');
    scanf('%d', &n);

    if (n < 5) {
        printf('城市数量太少，请重新运行程序。\n');
        return 0;
    }

    Graph* graph = createGraph(n);
    int i, j;
    int distance;
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            printf('请输入城市 %d 到城市 %d 的距离：', i, j);
            scanf('%d', &distance);
            addEdge(graph, i, j, distance);
        }
    }

    printf('\n邻接表：\n');
    printGraph(graph);

    printf('\n普利姆算法生成的最小生成树：\n');
    primMST(graph);

    printf('\n克鲁斯卡尔算法生成的最小生成树：\n');
    kruskalMST(graph);

    return 0;
}

主要函数说明

createNode函数：创建一个新的邻接表节点。
createGraph函数：创建一个具有指定数量顶点的图。
addEdge函数：向图中添加一条边，同时更新邻接表。
printGraph函数：输出邻接表。
primMST函数：使用普利姆算法生成最小生成树，并输出结果。
find函数：查找节点的根节点（并查集）。
Union函数：合并两个集合（并查集）。
compare函数：比较两个边的权值（用于快速排序）。
kruskalMST函数：使用克鲁斯卡尔算法生成最小生成树，并输出结果。
main函数：读取输入城市数量和距离，创建图，调用普利姆算法和克鲁斯卡尔算法生成最小生成树，并输出结果。

运行示例

编译代码：gcc network.c -o network
运行代码：./network

程序会提示用户输入城市数量和城市之间的距离，并最终输出两种算法生成的最小生成树结果。

总结

本代码通过C语言实现了最小生成树算法，并使用邻接表和邻接矩阵两种存储结构来表示城市之间的距离。代码结构清晰、易于理解，并通过示例演示了代码的运行过程。用户可以根据实际需求修改代码，并应用于其他网络建设场景中。