用c语言编写一个代码以实现在n个城市n=5之间建设网络只需保证连通即可要求最经济的架设方法。1手动录入城市数nn=5及各城市之间的距离并将其储存起来。2存储结构需采用邻接表和邻接矩阵两种。3在代码编写时需要采用普利姆算法和克鲁斯卡尔算法两种。4输出所得的邻接表或邻接矩阵。5输出所得的最小生成树需要包括节点及权值。并对主要函数进行说明

以下是一个使用C语言实现的最小生成树算法的示例代码。其中使用了邻接表和邻接矩阵两种存储结构，并分别采用了普利姆算法和克鲁斯卡尔算法来构建最小生成树。

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

// 定义最大城市数量
#define MAX_CITIES 100

// 邻接表中的链表节点
typedef struct Node {
    int city;
    int distance;
    struct Node* next;
} Node;

// 邻接表
typedef struct {
    Node* head;
} AdjList[MAX_CITIES];

// 邻接矩阵
typedef int AdjMatrix[MAX_CITIES][MAX_CITIES];

// 普利姆算法
void prim(int n, AdjList adjList, AdjMatrix adjMatrix) {
    int selected[MAX_CITIES]; // 记录已选中的城市
    int minDistance[MAX_CITIES]; // 记录到每个城市的最小距离
    int parent[MAX_CITIES]; // 记录每个城市的父节点
    int totalDistance = 0; // 记录最小生成树的总距离

    // 初始化数据
    for (int i = 0; i < n; i++) {
        selected[i] = 0;
        minDistance[i] = INT_MAX;
        parent[i] = -1;
    }

    // 从第一个城市开始构建最小生成树
    minDistance[0] = 0;

    for (int i = 0; i < n; i++) {
        int minIndex = -1;
        int min = INT_MAX;

        // 选取最小距离的城市
        for (int j = 0; j < n; j++) {
            if (!selected[j] && minDistance[j] < min) {
                min = minDistance[j];
                minIndex = j;
            }
        }

        selected[minIndex] = 1; // 将城市标记为已选中

        // 更新其他城市的最小距离和父节点信息
        for (Node* node = adjList[minIndex].head; node != NULL; node = node->next) {
            int city = node->city;
            int distance = node->distance;
            if (!selected[city] && distance < minDistance[city]) {
                minDistance[city] = distance;
                parent[city] = minIndex;
            }
        }
    }

    // 输出最小生成树的节点及权值
    printf("Prim Algorithm:\n");
    for (int i = 1; i < n; i++) {
        printf("Edge: %d - %d, Distance: %d\n", parent[i], i, adjMatrix[i][parent[i]]);
        totalDistance += adjMatrix[i][parent[i]];
    }
    printf("Total Distance: %d\n", totalDistance);
}

// 克鲁斯卡尔算法
void kruskal(int n, AdjList adjList, AdjMatrix adjMatrix) {
    int parent[MAX_CITIES]; // 记录每个城市的父节点
    int totalDistance = 0; // 记录最小生成树的总距离

    // 初始化父节点信息
    for (int i = 0; i < n; i++) {
        parent[i] = -1;
    }

    // 构建边集合
    typedef struct {
        int city1;
        int city2;
        int distance;
    } Edge;

    Edge edges[MAX_CITIES * MAX_CITIES];
    int numEdges = 0;

    for (int i = 0; i < n; i++) {
        for (Node* node = adjList[i].head; node != NULL; node = node->next) {
            if (i < node->city) {
                edges[numEdges].city1 = i;
                edges[numEdges].city2 = node->city;
                edges[numEdges].distance = node->distance;
                numEdges++;
            }
        }
    }

    // 对边集合按照距离进行排序
    for (int i = 0; i < numEdges - 1; i++) {
        for (int j = 0; j < numEdges - i - 1; j++) {
            if (edges[j].distance > edges[j + 1].distance) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }

    // 使用并查集判断边是否会形成环路
    int numSelectedEdges = 0;
    int index = 0;

    while (numSelectedEdges < n - 1 && index < numEdges) {
        Edge edge = edges[index++];
        int city1 = edge.city1;
        int city2 = edge.city2;

        while (parent[city1] != -1) {
            city1 = parent[city1];
        }
        while (parent[city2] != -1) {
            city2 = parent[city2];
        }

        if (city1 != city2) {
            parent[city2] = city1;
            printf("Edge: %d - %d, Distance: %d\n", edge.city1, edge.city2, edge.distance);
            totalDistance += edge.distance;
            numSelectedEdges++;
        }
    }

    printf("Total Distance: %d\n", totalDistance);
}

// 创建邻接表和邻接矩阵
void createGraph(int n, AdjList adjList, AdjMatrix adjMatrix) {
    // 初始化邻接表
    for (int i = 0; i < n; i++) {
        adjList[i].head = NULL;
    }

    // 手动录入城市之间的距离并将其存储起来
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int distance;
            printf("Enter distance between city %d and city %d: ", i, j);
            scanf("%d", &distance);

            // 更新邻接表
            Node* newNode = (Node*)malloc(sizeof(Node));
            newNode->city = j;
            newNode->distance = distance;
            newNode->next = adjList[i].head;
            adjList[i].head = newNode;

            newNode = (Node*)malloc(sizeof(Node));
            newNode->city = i;
            newNode->distance = distance;
            newNode->next = adjList[j].head;
            adjList[j].head = newNode;

            // 更新邻接矩阵
            adjMatrix[i][j] = distance;
            adjMatrix[j][i] = distance;
        }
    }
}

// 输出邻接表
void printAdjList(int n, AdjList adjList) {
    printf("Adjacency List:\n");
    for (int i = 0; i < n; i++) {
        printf("City %d:", i);
        for (Node* node = adjList[i].head; node != NULL; node = node->next) {
            printf(" -> City %d, Distance %d", node->city, node->distance);
        }
        printf("\n");
    }
}

// 输出邻接矩阵
void printAdjMatrix(int n, AdjMatrix adjMatrix) {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d\t", adjMatrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n;

    printf("Enter the number of cities (n >= 5): ");
    scanf("%d", &n);

    if (n < 5) {
        printf("Invalid number of cities.\n");
        return 0;
    }

    AdjList adjList;
    AdjMatrix adjMatrix;

    createGraph(n, adjList, adjMatrix);
    printAdjList(n, adjList);
    printAdjMatrix(n, adjMatrix);

    prim(n, adjList, adjMatrix);
    kruskal(n, adjList, adjMatrix);

    return 0;
}

主要函数说明：

• prim函数实现了普利姆算法，通过循环选择最小距离的城市，并更新其他城市的最小距离和父节点信息。最后输出最小生成树的节点及权值。
• kruskal函数实现了克鲁斯卡尔算法，首先构建边集合并按照距离进行排序，然后使用并查集判断边是否会形成环路。最后输出最小生成树的节点及权值。
• createGraph函数用于手动录入城市之间的距离，并更新邻接表和邻接矩阵。
• printAdjList函数用于输出邻接表。
• printAdjMatrix函数用于输出邻接矩阵。
• main函数为程序的入口，首先获取城市数量，然后创建邻接表和邻接矩阵，接着调用打印函数和最小生成树算法函数