图的最小生成树

发表于 更新于 分类于 ，
本文字数： 2.9k

最小生成树 —— 包含 原图 中的所有 n 个结点 并且 有保持图连通的最少的边

一个有 n 个结点的 连通图 的生成树是 原图 的 极小连通子图

数据结构课代码实现 之 最小生成树

简要理解

求图的最小生成树的两种算法：Prim（适用于稠密图） 与 Kruskal （适用于稀疏图）

Prim算法

维护一个 点集合 和一个 边集合 用来保存最小生成树，点集合初始只有一个存在于该图的点，边集合初始为空集

每次更新操作都是寻找一条边 (u, v)，将该边并入边集合中，将点 v 并入点集合中

点 u 为当前点集合中的一个点，点 v 为不在点集合中的一个点

边 (u, v) 满足条件为不在边集合中并且代价最小

直至图中的所有点都进入点集合 此时边集合中必有 图的点数 - 1条边

Kruskal算法

令最小生成树的初始状态为只有 n 个顶点而无边的非连通图，图中每个点都是一个连通分量

将所有图中所有边按照权值大小由小到大排序

按次序对边进行检查，如果当前边依附的顶点落在不同的连通分量上，则将此边加入至最小生成树中

否则舍弃此边继续检查下一条代价最小的边

直至所有顶点都在同一个连通分量上

附上之前的文章：

最小生成树

代码实现

用邻接矩阵的储存结构实现

Prim代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
struct close
{
    int adjvex;
    int lowcost;
    int pos;
}closeedge[MAX_VERTEX_NUM];    // 开一个结构体数组储存图中所有点到集合的距离

bool cmp(close a, close b)
{
    if(a.lowcost < b.lowcost)
        return true;
    return false;    
}

int mininum(int num, close* closeedge)
{
    close closeedge1[num];      // 另开一个结构体数组用来排序

    for(int i = 0;i < num;i++)
    {
        closeedge1[i].adjvex = closeedge[i].adjvex;
        closeedge1[i].lowcost = closeedge[i].lowcost;
        closeedge1[i].pos = closeedge[i].pos;
    }
    
    sort(closeedge1, closeedge1 + num, cmp);

    for(int i = 0;i < num;i++)
        if(closeedge1[i].lowcost > 0)            // 把已在集合中的边设 0（对应点到集合cost 为 0）
            return closeedge1[i].pos;
}

void MiniSpanTree_PRIM(MGraph G, int u)
{
    int k = LocateVex(G, u);
    for(int j = 0;j < G.vexnum;j++)
        if(j != k)
            closeedge[j] = {u, G.arcs[k][j].adj, j};
	closeedge[k].pos = k;
	closeedge[k].lowcost = 0;
    for(int i = 1;i < G.vexnum;i++)
    {
        k = mininum(G.vexnum, closeedge);
        cout << closeedge[k].adjvex << " " << G.vexs[k] << endl;
        closeedge[k].lowcost = 0;
        for(int j = 0;j < G.vexnum;j++)
            if(G.arcs[k][j].adj < closeedge[j].lowcost)
                closeedge[j] = {G.vexs[k], G.arcs[k][j].adj, j};        // 用新加入的点更新其余所有点到集合的代价
    }
}

int main()
{
    MGraph a;
    CreateGraph(a);
    MiniSpanTree_PRIM(a, 2);
    return 0;
}

Kruskal代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct edge
{
    int st;
    int en;
    int cost;
};

int fa[MAX_VERTEX_NUM], peo[MAX_VERTEX_NUM];        // 并查集检查两个点是否存在于一个连通分量中
                                                    // peo数组 保存当前集合元素个数
int find(int x)             // 并查集 find 操作
{
    if(fa[x] != x)
        return fa[x] = find(fa[x]);
    else
        return x;
}

bool cmp(edge a, edge b)
{
    if(a.cost < b.cost)
        return true;
    return false;
}

void Kruskal(MGraph &G)
{
    int num = 2 * G.arcnum;         // 无向图乘二
    struct edge edges[num];
    int cnt = 0;
    for(int i = 0;i < G.vexnum;i++)
    {
        for(int j = 0;j < G.vexnum;j++)
        {
            if(G.arcs[i][j].adj < INFINITY)
                edges[cnt++] = {i, j, G.arcs[i][j].adj};
        }
    }

    sort(edges, edges + num, cmp);

    for(int i = 0;i < G.vexnum;i++)
    {
        fa[i] = i;
        peo[i] = 1;
    }

    for(int j = 0;j < num;j++)
    {
        int x = edges[j].st, y = edges[j].en;
        x = find(x);
        y = find(y);
        if(x != y)
        {
            fa[y] = x;
            peo[x] += peo[y];       // 更新集合成员数
            cout << "起点：" << " " << G.vexs[edges[j].st] << "终点：" << " " << G.vexs[edges[j].en] << "权值：" << edges[j].cost << endl;
        }

        if(peo[x] == G.vexnum)
            break;                  // 如果 集合点数 与 图的点数相同 生成树建立完毕
    }
}

int main()
{
    MGraph a;
    CreateGraph(a);
    Kruskal(a);
    return 0;
}