C语言实现最小生成树算法：普利姆算法和克鲁斯卡尔算法

本代码使用C语言实现了在n个城市之间建设网络并找出最经济的架设方法，使用了普利姆算法和克鲁斯卡尔算法两种算法，并采用邻接表和邻接矩阵两种存储结构。

代码实现

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

#define MAX 100

// 邻接表中的节点结构
typedef struct Node {
    int city;  // 城市编号
    int dist;  // 城市之间的距离
    struct Node* next;  // 指向下一个节点的指针
} Node;

// 邻接表结构
typedef struct List {
    Node* head;  // 指向链表的头节点的指针
} List;

// 邻接矩阵结构
typedef struct Matrix {
    int** graph;  // 存储城市之间距离的二维数组
    int size;     // 城市数量
} Matrix;

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

// 创建邻接表
List* createList(int size) {
    List* newList = (List*)malloc(sizeof(List));
    newList->head = (Node*)malloc(size * sizeof(Node));
    for (int i = 0; i < size; i++) {
        newList->head[i].next = NULL;
    }
    return newList;
}

// 添加节点到邻接表
void addNode(List* list, int src, int dest, int dist) {
    Node* newNode = createNode(dest, dist);
    newNode->next = list->head[src].next;
    list->head[src].next = newNode;
}

// 创建邻接矩阵
Matrix* createMatrix(int size) {
    Matrix* newMatrix = (Matrix*)malloc(sizeof(Matrix));
    newMatrix->graph = (int**)malloc(size * sizeof(int*));
    for (int i = 0; i < size; i++) {
        newMatrix->graph[i] = (int*)malloc(size * sizeof(int));
        for (int j = 0; j < size; j++) {
            newMatrix->graph[i][j] = 0;
        }
    }
    newMatrix->size = size;
    return newMatrix;
}

// 添加边到邻接矩阵
void addEdge(Matrix* matrix, int src, int dest, int dist) {
    matrix->graph[src][dest] = dist;
    matrix->graph[dest][src] = dist;
}

// 打印邻接表
void printList(List* list, int size) {
    for (int i = 0; i < size; i++) {
        printf("城市 %d: ", i);
        Node* currentNode = list->head[i].next;
        while (currentNode != NULL) {
            printf("%d (距离：%d) ", currentNode->city, currentNode->dist);
            currentNode = currentNode->next;
        }
        printf("\n");
    }
}

// 打印邻接矩阵
void printMatrix(Matrix* matrix) {
    for (int i = 0; i < matrix->size; i++) {
        for (int j = 0; j < matrix->size; j++) {
            printf("%d ", matrix->graph[i][j]);
        }
        printf("\n");
    }
}

// 普利姆算法
void primAlgorithm(Matrix* matrix) {
    int selected[matrix->size];  // 记录已选择的节点
    int parent[matrix->size];    // 记录每个节点的父节点
    int minDist[matrix->size];   // 记录每个节点到最小生成树的距离

    // 初始化数组
    for (int i = 0; i < matrix->size; i++) {
        selected[i] = 0;
        minDist[i] = MAX;
    }

    // 从第一个节点开始
    minDist[0] = 0;
    parent[0] = -1;

    for (int i = 0; i < matrix->size - 1; i++) {
        int minIndex, min;
        min = MAX;

        // 选择最小的距离节点
        for (int j = 0; j < matrix->size; j++) {
            if (selected[j] == 0 && minDist[j] < min) {
                min = minDist[j];
                minIndex = j;
            }
        }

        selected[minIndex] = 1;

        // 更新距离数组和父节点数组
        for (int j = 0; j < matrix->size; j++) {
            if (matrix->graph[minIndex][j] && selected[j] == 0 &&
                matrix->graph[minIndex][j] < minDist[j]) {
                parent[j] = minIndex;
                minDist[j] = matrix->graph[minIndex][j];
            }
        }
    }

    // 输出最小生成树
    printf("普利姆算法最小生成树:\n");
    printf("节点\t父节点\t权值\n");
    for (int i = 1; i < matrix->size; i++) {
        printf("%d\t%d\t%d\n", i, parent[i], matrix->graph[i][parent[i]]);
    }
}

// 克鲁斯卡尔算法
void kruskalAlgorithm(Matrix* matrix) {
    int parent[matrix->size];  // 记录每个节点的父节点

    // 初始化数组
    for (int i = 0; i < matrix->size; i++) {
        parent[i] = i;
    }

    int edges = 0;
    int minIndex, min, u, v;
    printf("克鲁斯卡尔算法最小生成树:\n");
    printf("节点\t父节点\t权值\n");
    while (edges < matrix->size - 1) {
        min = MAX;

        // 找到最小边
        for (int i = 0; i < matrix->size; i++) {
            for (int j = 0; j < matrix->size; j++) {
                if (matrix->graph[i][j] && matrix->graph[i][j] < min) {
                    min = matrix->graph[i][j];
                    u = i;
                    v = j;
                }
            }
        }

        // 找到父节点
        while (parent[u] != u) {
            u = parent[u];
        }
        while (parent[v] != v) {
            v = parent[v];
        }

        // 判断是否会形成环
        if (u != v) {
            printf("%d\t%d\t%d\n", v, u, min);
            parent[v] = u;
            edges++;
        }

        matrix->graph[u][v] = MAX;
    }
}

int main() {
    int n;
    printf("请输入城市数（n>=5）：");
    scanf("%d", &n);

    // 创建邻接表
    List* list = createList(n);

    // 创建邻接矩阵
    Matrix* matrix = createMatrix(n);

    // 手动录入城市之间的距离并储存起来
    printf("请录入城市之间的距离：\n");
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist;
            printf("城市 %d 到城市 %d 的距离：", i, j);
            scanf("%d", &dist);
            addNode(list, i, j, dist);
            addEdge(matrix, i, j, dist);
        }
    }

    // 输出邻接表和邻接矩阵
    printf("\n邻接表：\n");
    printList(list, n);
    printf("\n邻接矩阵：\n");
    printMatrix(matrix);

    // 使用普利姆算法找出最小生成树
    primAlgorithm(matrix);

    // 使用克鲁斯卡尔算法找出最小生成树
    kruskalAlgorithm(matrix);

    return 0;
}

主要函数说明

• createNode：创建节点，用于邻接表中的节点结构。
• createList：创建邻接表，用于存储城市之间的距离。
• addNode：将节点添加到邻接表中。
• createMatrix：创建邻接矩阵，用于存储城市之间的距离。
• addEdge：将边添加到邻接矩阵中。
• printList：打印邻接表。
• printMatrix：打印邻接矩阵。
• primAlgorithm：使用普利姆算法找出最小生成树。
• kruskalAlgorithm：使用克鲁斯卡尔算法找出最小生成树。
• main：主函数，用于手动录入城市之间的距离，并调用其他函数实现最小生成树的查找和输出。

代码说明

• 本代码首先定义了邻接表和邻接矩阵的结构体，并分别创建了相应的创建和添加节点/边的函数。
• 随后实现了普利姆算法和克鲁斯卡尔算法，分别利用邻接矩阵计算最小生成树。
• 在主函数中，用户输入城市数量和城市之间的距离，代码会构建邻接表和邻接矩阵，并调用普利姆算法和克鲁斯卡尔算法计算最小生成树，最终输出结果。

使用说明

1. 将代码保存为.c文件，并使用C语言编译器进行编译。
2. 运行可执行文件，程序会提示用户输入城市数量和城市之间的距离。
3. 输入完数据后，程序会输出邻接表、邻接矩阵和两种算法计算得到的最小生成树。

总结

本代码实现了使用C语言实现最小生成树算法，包括普利姆算法和克鲁斯卡尔算法，并采用邻接表和邻接矩阵两种存储结构，可以帮助用户计算n个城市之间建设网络的最经济方案。