最小生成树，采用普里姆算法和克鲁斯卡尔算法分别输出

Question

#普里姆算法
#克鲁斯卡尔算法
#分布解析
对于如图所示的无向带权图采用普里姆算法和克鲁斯卡尔算法分别输出图的领接矩阵存储和从顶点0出发的最小生成树。
对每一步需要详细解析，麻烦各位。

Answer 1

以下是使用C语言实现普里姆算法和克鲁斯卡尔算法生成最小生成树并输出领接矩阵存储的代码，有用请采纳呦：

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

// 图的最大顶点数
#define MAX_VERTICES 10

// 图的边类型
typedef struct {
    int u;
    int v;
    int w;
} Edge;

// 图类型
typedef struct {
    Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
    int n;  // 图中顶点数
} Graph;

// 最小堆类型
typedef struct {
    int *data;
    int size;
} MinHeap;

// 构建图
void createGraph(Graph *g) {
    g->n = 5;

    g->edges[0] = (Edge) {0, 1, 2};
    g->edges[1] = (Edge) {0, 3, 6};
    g->edges[2] = (Edge) {1, 2, 3};
    g->edges[3] = (Edge) {1, 3, 8};
    g->edges[4] = (Edge) {1, 4, 5};
    g->edges[5] = (Edge) {2, 4, 7};
    g->edges[6] = (Edge) {3, 4, 9};
}

// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 最小堆的上移操作
void siftUp(MinHeap *heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap->data[i] >= heap->data[parent]) {
            break;
        }
        swap(&heap->data[i], &heap->data[parent]);
        i = parent;
    }
}

// 最小堆的下移操作
void siftDown(MinHeap *heap, int i) {
    while (2 * i + 1 < heap->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int min_index = i;
        if (heap->data[left] < heap->data[min_index]) {
            min_index = left;
        }
        if (right < heap->size && heap->data[right] < heap->data[min_index]) {
            min_index = right;
        }
        if (min_index == i) {
            break;
        }
        swap(&heap->data[i], &heap->data[min_index]);
        i = min_index;
    }
}

// 将元素插入最小堆
void insert(MinHeap *heap, int x) {
    heap->data[heap->size++] = x;
    siftUp(heap, heap->size - 1);
}

// 从最小堆中取出最小元素
int extractMin(MinHeap *heap) {
    int min_value = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    siftDown(heap, 0);
    return min_value;
}

// 判断最小堆是否为空
int isHeapEmpty(MinHeap *heap) {
    return (heap->size == 0);
}

// 初始化最小堆
void initHeap(MinHeap *heap, int *data, int size) {
    heap->data = data;
    heap->size = size;
    for (int i = (size - 2) / 2; i >= 0; i--) {
        siftDown(heap, i);
    }
}

// 普里姆算法生成最小生成树
void prim(Graph *g, int *parent) {
    // 初始化parent和dist数组
    for (int i = 0; i < g->n; i++) {
        parent[i] = -1;
    }

    int dist[g->n];
    for (int i = 0; i < g->n; i++) {
        dist[i] = INT_MAX;
    }

    // 从顶点0开始搜索
    dist[0] = 0;
    MinHeap heap;
    int heap_data[MAX_VERTICES];
    initHeap(&heap, heap_data, 0);
    insert(&heap, 0);

    while (!isHeapEmpty(&heap)) {
        int u = extractMin(&heap);
        for (int i = 0; i < g->n; i++) {
            if (i != u) {
                for (int j = 0; j < g->n * (g->n - 1) / 2; j++) {
                    Edge e = g->edges[j];
                    if ((e.u == u && e.v == i) || (e.u == i && e.v == u)) {
                        if (dist[i] > e.w) {
                            dist[i] = e.w;
                            parent[i] = u;
                            insert(&heap, i);
                        }
                        break;
                    }
                }
            }
        }
    }
}

// 克鲁斯卡尔算法生成最小生成树
void kruskal(Graph *g, int *parent) {
    // 初始化parent数组
    for (int i = 0; i < g->n; i++) {
        parent[i] = i;    
    }

    int m = g->n * (g->n - 1) / 2;
    Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
    for (int i = 0; i < m; i++) {
        edges[i] = g->edges[i];
    }

    // 对edges数组按边权进行排序
    for (int i = 0; i < m - 1; i++) {
        for (int j = i + 1; j < m; j++) {
            if (edges[i].w > edges[j].w) {
                Edge temp = edges[i];
                edges[i] = edges[j];
                edges[j] = temp;
            }
        }
    }

    // 构建最小生成树
    for (int i = 0; i < m; i++) {
        Edge e = edges[i];
        int u = e.u;
        int v = e.v;
        while (u != parent[u]) {
            u = parent[u];
        }
        while (v != parent[v]) {
            v = parent[v];
        }
        if (u != v) {
            parent[u] = v;
        }
    }
}

// 输出领接矩阵存储的图
void printGraph(Graph *g) {
    int matrix[MAX_VERTICES][MAX_VERTICES] = {0};
    for (int i = 0; i < g->n * (g->n - 1) / 2; i++) {
        Edge e = g->edges[i];
        matrix[e.u][e.v] = matrix[e.v][e.u] = e.w;
    }
    for (int i = 0; i < g->n; i++) {
        for (int j = 0; j < g->n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    Graph g;
    createGraph(&g);

    int parent[MAX_VERTICES];
    prim(&g, parent);
    printf("Prim:\n");
    for (int i = 1; i < g.n; i++) {
        printf("(%d, %d)\n", parent[i], i);
    }
    printGraph(&g);

    kruskal(&g, parent);
    printf("Kruskal:\n");
    for (int i = 1; i < g.n; i++) {
        printf("(%d, %d)\n", parent[i], i);
    }
    printGraph(&g);

    return 0;
}

该程序中，首先定义了图和边的结构体，定义了最小堆的结构体和操作函数，并实现了普里姆算法和克鲁斯卡尔算法生成最小生成树的函数。其中，最小堆采用数组实现，每个元素的值为某个顶点的下标，插入元素和取出最小元素的时间复杂度均为$O(logn)$。对于每个算法，都先初始化parent数组和dist数组，然后根据算法的不同，进行不同的操作。最后，输出生成的最小生成树和领接矩阵存储的图。