【数据结构】图论——Prim算法和Kruskal算法

Prim算法和Kruskal算法

文章: 【数据结构】图论（图的储存方式，图的遍历算法DFS和BFS、图的遍历算法的应用、图的连通性问题）

Prim算法的原理

初始化：从图中的一个起始顶点开始，逐步将权值最小的边添加到生成树中。
扩展生成树：在每一步中，选择当前生成树中所有顶点到生成树外所有顶点中权值最小的一条边，并将该边和对应的顶点加入生成树。
重复上述步骤：直到所有顶点都包含在生成树中。

数据结构

图采用邻接矩阵和邻接表存放均可。下面以邻接矩阵为例实现Prim算法：

图的表示：用一个二维数组arcs表示图的邻接矩阵，arcs[i][j]表示顶点i到顶点j之间的边的权值。vexnum表示图的顶点数，arcnum表示边的数量。
边的类型：EdgeType结构体用于存放每个顶点到生成树中顶点的最小权值边的信息。adjvex表示这条边连接的另一个顶点，lowcost表示这条边的权值。

#define MAX 100
#define MAXEDGE 1000000

typedef struct {
    int arcs[MAX][MAX];
    int vexnum, arcnum;
} AGraphs;

typedef struct {
    int adjvex; // 与生成树中的点连接的最好情况，记录的是与生成树中的哪个点（记录的是点的位置）
    int lowcost; // 记录的是该最好情况的弧的权重
} EdgeType;

EdgeType closedge[MAX]; // 采用一维数组closedge[MAX]存放图中每个顶点与生成树中顶点相连的最好情况

算法步骤解释

初始化closedge数组：

void prim(AGraphs G, int u) {
    int i, j, k;
    EdgeType closedge[MAX];

    for (j = 0; j < G.vexnum; j++) {
        closedge[j].adjvex = u; // 此次选中的与生成树中连接情况最好的点的位置
        closedge[j].lowcost = G.arcs[u][j]; // 记录下来这个数值的大小
    }

    closedge[u].lowcost = 0; // 如果顶点已经包含在生成树中，则lowcost设为0。

逐步扩展生成树：

    for (i = 1; i < G.vexnum; i++) {
        k = minclosedge(closedge);
        printf("(%d,%d)\n", closedge[k].adjvex, k);
        closedge[k].lowcost = 0;

        for (j = 0; j < G.vexnum; j++) {
            if (G.arcs[k][j] < closedge[j].lowcost) {
                closedge[j].lowcost = G.arcs[k][j];//选中
                closedge[j].adjvex = k; //选中
            }
        }
    }
}

找最小权值边：

int minclosedge(EdgeType closedge[]) {
    int min = MAXEDGE, j, k = -1;
    for (j = 0; j < G.vexnum; j++) {
        if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {
            min = closedge[j].lowcost; //选中
            k = j;
        }
    }
    return k;
}

算法实现

每一步只保留不在生成树中的点和生成树相连的最好情况

实现算法时，在每一步我们只保留不在生成树中的点和生成树相连的最好情况，而不是考察不在生成树中的点和生成树相连的所有情况。
每次加入一个顶点和一条边进入生成树后，我们都考察一下不在生成树中的点和生成树中的点相连的最好情况是否被新加入的点更新。

代码示例

#define MAX 100
#define MAXEDGE 1000000

typedef struct {
    int arcs[MAX][MAX];
    int vexnum, arcnum;
} AGraphs;

typedef struct {
    int adjvex;
    int lowcost;
} EdgeType;

// 采用一维数组closedge[MAX]存放图中每个顶点与生成树中顶点相连的最好情况

/*
当顶点v尚未加入生成树时，closedge[v]存放的是v与生成树中的顶点相连的最好情况：
v与生成树中的顶点的所有连边中权值最小的那条边；
closedge[v].adjvex存放的这条权值最小的边的另一个顶点，
closedge[v].lowcost存放的这条权值最小的边的权值。

如何区分生成树中的顶点和不在生成树中的顶点呢？

closedge[w].lowcost==0表示w已经加入生成树
*/

void prim(AGraphs G, int u) {
    int i, j, k;
    EdgeType closedge[MAX];

    for (j = 0; j < G.vexnum; j++) {
        closedge[j].adjvex = u; // 此次选中的与生成树中连接情况最好的点的位置
        closedge[j].lowcost = G.arcs[u][j]; // 记录下来这个数值的大小
    }

    closedge[u].lowcost = 0; // 如果顶点已经包含在生成树中，则lowcost设为0。

    for (i = 1; i < G.vexnum; i++) {
        k = minclosedge(closedge);
        printf("(%d,%d)\n", closedge[k].adjvex, k);
        closedge[k].lowcost = 0;

        for (j = 0; j < G.vexnum; j++) {
            if (G.arcs[k][j] < closedge[j].lowcost) {
                closedge[j].lowcost = G.arcs[k][j];
                closedge[j].adjvex = k;
            }
        }
    }
}

int minclosedge(EdgeType closedge[]) {
    int min = MAXEDGE, j, k = -1;
    for (j = 0; j < G.vexnum; j++) {
        if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {
            min = closedge[j].lowcost;
            k = j;
        }
    }
    return k;
}

// 时间复杂度：O(n^2) Prim算法适合于稠密图

画图求解：

在这里插入图片描述
时间复杂度： $O(n^2)$
Prim算法适合于稠密图

问法
最小生成树的求解过程
文字叙述画表求解过程
伪码描述（上述程序）

Kruskal 算法

先排序，对所有边按照权值升序排序
从小开始加，只要不产生回路，最后加到 $n - 1$
需要排序（适合于吸收图）

Kruscal算法适合稀疏图，时间复杂度为O(eloge)，e为图的边数，因为该算法要对边按照权值排序，（堆、快速。归并）排序算法的平均时间复杂度O(eloge)

Kruskal算法是一种用于查找加权无向图的最小生成树（MST）的贪心算法。它通过逐步选择权值最小的边并确保不会形成环来构建最小生成树。下面详细描述Kruskal算法的实现过程：

Kruskal算法的原理和步骤

初始化：
- 创建一个包含所有图中顶点的集合，每个顶点初始时在不同的集合中。
- 初始化最小生成树为空。
排序：
- 将图中的所有边按权值从小到大排序。
逐步构建生成树：
- 依次检查排序后的每一条边，如果该边连接的两个顶点位于不同的集合中，则将这条边加入最小生成树，并合并这两个顶点所在的集合。
- 如果该边连接的两个顶点已经在同一集合中，则跳过这条边，以避免形成环。
终止条件：
- 当最小生成树包含的边数等于图中顶点数减一时，算法终止。

Kruskal算法的实现

为了实现Kruskal算法，需要使用**并查集（Disjoint Set Union, DSU）**数据结构来管理和合并顶点集合，并检查是否会形成环。

以下是Kruskal算法的详细实现步骤和代码示例：

数据结构

#define MAX 100
#define MAXEDGE 1000000

typedef struct {
    int u, v;  // 边的两个顶点
    int weight;  // 边的权值
} Edge;

typedef struct {
    Edge edges[MAXEDGE];  // 图中的所有边
    int vexnum, edgenum;  // 顶点数和边数
} Graph;

int parent[MAX];  // 并查集数组
int rank[MAX];    // 并查集的秩数组（用于路径压缩优化）

并查集操作

// 查找操作，带路径压缩
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 合并操作，带按秩合并
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

Kruskal算法

// 边的比较函数，用于排序
int cmp(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}

// Kruskal算法
void kruskal(Graph G) {
    int i;
    Edge result[MAX];  // 用于存储最小生成树中的边
    int e = 0;  // 最小生成树中的边数

    // 初始化并查集
    for (i = 0; i < G.vexnum; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    // 按边的权值排序
    qsort(G.edges, G.edgenum, sizeof(Edge), cmp);

    for (i = 0; i < G.edgenum; i++) {
        Edge nextEdge = G.edges[i];

        int x = find(nextEdge.u);
        int y = find(nextEdge.v);

        // 如果这条边不会形成环
        if (x != y) {
            result[e++] = nextEdge;  // 将边加入结果中
            unionSet(x, y);  // 合并两个顶点的集合
        }
    }

    // 打印最小生成树
    printf("Following are the edges in the constructed MST:\n");
    for (i = 0; i < e; i++) {
        printf("%d -- %d == %d\n", result[i].u, result[i].v, result[i].weight);
    }
}