数据结构与算法-最小生成树

个人来看，Prim算法、Kruskal算法都可以算贪婪算法。

0. 数据结构

采用邻接矩阵实现。

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef struct {
    int arc[MAXVEX][MAXVEX];
    int numVertices, numEdges;
} MGraph;

1. Prim算法

1.1核心思路

从一个顶点出发，不断贪婪已知可以连接的最小权值边。

• 一个adjvex数组不断更新相连，且权值更小的顶点。
  • adjvex中是起点，。
• 一个lowcost数组不断更新可选的最小权值，通过0标记已加入最小生成树。
  • lowcost中存储的权值，新顶点指向k的权值更小，就会更新。

1.2 实现

void MiniSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    int sum = 0;
    
    int count = G.numVertices;
    int *lowcost = (int *)malloc(sizeof(int) * count); // adjvex[k]和k相连可选的最小权值，通过0标记已加入最小生成树
    int *adjvex = (int *)malloc(sizeof(int) * count); // adjvex[k]和k相连，且权值更小，adjvex中存的是起点
    
    // 1.从v0顶点开始，通过0标记已加入最小生成树
    lowcost[0] = 0;
    adjvex[0] = 0;
    
    // 2.第一次由v0初始化
    for (i = 1; i < count; i++) {
        lowcost[i] = G.arc[0][i]; // 读入v0的邻接矩阵
        adjvex[i] = 0; // 存储和0相连的最小权值
    }
    
    for (i = 1; i < count; i++) { // 循环除了v0以外的全部顶点
        // 2.找到最小权值的边和相连的顶点adjvex[k]和k
        min = INFINITYC; // 初始化最小权值为最大值
        k = 0; // 默认从v0开始
        for (j = 1; j < count; j++) { // 找到最小权值的边
            if (lowcost[j] != 0 // 没有加入到最小生成树
               && lowcost[j] < min) { // 权值比min更小
                min = lowcost[j]; // 更新最小值
                k = j; // 记录下最小值的下标
            }
        }
        // adjvex[k]和k相连
        printf("(%d, %d) = %d\n", adjvex[k], k, min);// 打印当前顶点边中权值最小的边
        sum += min; // 计算总权值
        
        // 3.将当前顶点的权值设置为0，表示已加入最小生成树
        lowcost[k] = 0;
        
        // 4.更新lowcost和adjvex(从新顶点到其他各顶点会不会更小)
        // lowcost: 可选的最小权值，通过0标记已加入最小生成树
        // adjvex: adjvex[k]和k相连，且权值更小
        for (j = 1; j < count; j++) {
            if (lowcost[j] != 0 // 没有加入到最小生成树
               && G.arc[k][j] < lowcost[j]) { // 从vk到j存在更小权值的边
                lowcost[j] = G.arc[k][j]; // 将较小的权值存入lowcost相应位置
                adjvex[j] = k; // 将下标为k的顶点存入adjvex
            }
        }
    }
    printf("sum = %d\n", sum); // 打印总权值
    
    free(adjvex);
    free(lowcost);
}

2. Kruskal算法

2.1 核心思路

全局贪婪最小权值的边(通过排序)，同时防止形成环。

如何防止形成环：

• 通过一个数组，记录边的开头和结尾沿着路径到达尾部的时候的顶点。
• 遍历边，判断边的开头和结尾沿着路径到达尾部的时候，是否会来到同一个顶点。
  • 如果来到同一个顶点，说明形成环。
  • 如果来到了不同的顶点，说明没有形成环。

2.2 实现

// 边表的结构体
typedef struct {
    int begin;
    int end;
    int weight;
} Edge;

// 交换结构体
void swap(Edge *a, Edge *b) {
    Edge tmp = *a;
    *a = *b;
    *b = tmp;
}

// 冒泡排序
void sort(Edge *edges, int n) {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (edges[j].weight > edges[j+1].weight)
                swap(&edges[j], &edges[j+1]);
        }
    }
}

void MiniSpanTree_Kruskal(MGraph G) {
    int sum = 0;
    int *tail = (int *)calloc(G.numVertices, sizeof(int)); // 辅助查找尾部顶点，并初始化
    Edge *edges = (Edge *)malloc(sizeof(Edge) * G.numEdges); // 边表
    
    // 1.构建边表数组(无向图，对角线上半部分)
    int k = 0;
    for (int i = 0; i < G.numVertices-1; i++) {
        for (int j = i + 1; j < G.numVertices; j++) {
            if (G.arc[i][j] < INFINITYC) { // 存在可到达的边
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                k++;
            }
        }
    }
    
    // 2.对边表数组排序
    sort(edges, G.numEdges);
    
    //3. 计算最小生成树
    printf("打印最小生成树：\n");
    for (int i = 0; i < G.numEdges; i++) { // 遍历边表
        // 遍历边，判断边的开头和结尾沿着路径到达尾部的时候，是否会来到同一个顶点
        int n = FindTail(tail, edges[i].begin); // 从起点找到尾部
        int m = FindTail(tail, edges[i].end); // 从终点找到尾部
        if (n != m) { // n与m不等，说明不会形成环路
            tail[n] = m; // 从n出发，尾部是m
            printf("(%d, %d) = %d\n", edges[i].begin, edges[i].end, edges[i].weight); // 打印最小生成树路径
            sum += edges[i].weight;  // 计算总权值
        }
    }
    
    printf("sum = %d\n", sum); // 打印总权值
    
    free(edges);
    free(tail);
}