devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图——最小生成树_求下图的最小生成树

作者：Monodyee | 2024-03-15 17:52:58

赞

踩

求下图的最小生成树

图——最小生成树

1. 基本概念

在一个连通无向图G=(V, E)中，对于其中的每条边(u,v)∈E，赋予其权重w(u, v)，则最小生成树问题就是要在G中找到一个连通图G中所有顶点的无环子集T⊆E，使得这个子集中所有边的权重之和w(T) = ∑ ( u , v ) ∈ T w ( u , v ) \displaystyle\sum_{(u,v)∈T} w(u, v) (u,v)∈T∑​w(u,v)最小。显然，T必然是一棵树，这样的树通常称为图G的生成树。

2. 最小生成树算法

通常来说，要解决最小生成树问题，通常采用两种算法：Prim算法和Kruskal算法。先假设要求一个连通无向图G=(V, E)的最小生成树T，且以其中的一个顶点V1为T的根结点。下面就分别对这两种算法进行介绍。

2.1 Prim算法

2.1.1 基本思想

Prim算法构建最小生成树的过程是：先构建一棵只包含根结点V1的树A，然后每次在连接树A结点和图G中树A以外的结点的所有边中，选取一条权重最小的边加入树A，直至树A覆盖图G中的所有结点。

注意：在这个算法中，关键点在于在连接树A结点和图G中树A以外的结点的所有边中选取权重最小的边。在算法实现过程中，要记录G中每个结点i到树A中结点的最小距离minidistance[i]，以及与之相连的树A中的那个结点miniadj[i]。minidistance[i]开始都初始化为无穷大，miniadj[i]都初始化为该顶点自己；每将一个结点j加入了树A，首先令minidistance[j]=0，然后遍历图G中所有不在树A中的结点，看看往树A中加入了结点j后，这些结点到树A中结点的最小距离会不会变小，如果变小则进行调整。例如，对于结点k，它在图G中，但不在树A中，且结点k与结点j相连，该边的权重为w(k, j)。在未将结点j加入树A前，结点k到树A中结点的最小距离为minidistance[k]；将结点j加入树A后，如果minidistance[k] > w(k, j)，那么结点k到树A中结点的最小距离就是结点k到结点j的最小距离，所以要将minidistance[k]调整为w(k, j)，且miniadj[k]为j。

例子
有一个无向连通图G，它有5个顶点，7条边，如下图所示。
在这里插入图片描述
以结点A最为根结点，利用Prim算法来生成该图的最小生成树T的过程如下：
（1）开始T为空，初始化minidistance[A] = minidistance[B] = minidistance[C] = minidistance[D] = minidistance[E] = ∞ {\infty} ∞，miniadj[A] = A，miniadj[B] = B, miniadj[C] = C，miniadj[D] = D，miniadj[E] = E；

（2）将结点A加入T，这时minidistance[A] = 0，miniadj[A] = A， minidistance[B] = 6，miniadj[B] = A ，minidistance[C] = 1，miniadj[C] = A , minidistance[D] = 4，miniadj[D] = A , minidistance[E] = 4,miniadj[E] = A 。

（3）此时结点B,C,D,E都不在树T中，在连接树T结点和图G中树A以外的结点的所有边中，权重最小的边是minidistance[C]，且miniadj[C]=A，所以将结点C和结点C与结点A连成的边加入树T。此时，minidistance[A] = 0，miniadj[A] = A， minidistance[B] = 6，miniadj[B] = A ，minidistance[C] = 0，miniadj[C] = A , minidistance[D] = 4，miniadj[D] = A , minidistance[E] = 4,miniadj[E] = A 。

（4）此时结点B,D,E都不在树T中，在连接树T结点和图G中树A以外的结点的所有边中，权重最小的边是minidistance[D]和minidistance[E]，从中随便选一个，此处选结点D，且miniadj[D]=A，所以将结点D和结点D与结点A连成的边加入树T。此时，minidistance[A] = 0，miniadj[A] = A， minidistance[B] = 2，miniadj[B] = D ，minidistance[C] = 0，miniadj[C] = A , minidistance[D] = 0，miniadj[D] = A , minidistance[E] = 4,miniadj[E] = A 。

（5）此时结点B,E都不在树T中，在连接树T结点和图G中树A以外的结点的所有边中，权重最小的边是minidistance[B]，且miniadj[B]=D，所以将结点B和结点B与结点D连成的边加入树T。此时，minidistance[A] = 0，miniadj[A] = A， minidistance[B] = 0，miniadj[B] = D ，minidistance[C] = 0，miniadj[C] = A , minidistance[D] = 0，miniadj[D] = A , minidistance[E] = 2,miniadj[E] = B。

（6）此时只有结点E都不在树T中，因此在连接树T结点和图G中树A以外的结点的所有边中，权重最小的边是minidistance[E]，且miniadj[E]=B，所以将结点E和结点E与结点B连成的边加入树T，此时最小生成树构成，如下图所示：
在这里插入图片描述

2.1.2 代码实现
#define Maximum 1000
#define Biggest 100000000

typedef struct EdgeListNode{
    int adjId;
    int weight;
    EdgeListNode* next;
};

typedef struct VertexListNode{
    int data;
    EdgeListNode* firstadj;
};

typedef struct GraphAdjList{
    int vertexnumber;
    int edgenumber;
    VertexListNode vertextlist[Maximum];
};

typedef struct MiniTreeEdge {
    int s;
    int e;
    int weight;
    MiniTreeEdge *next;
};

typedef struct MiniTree {  //最小生成树
    MiniTreeEdge *head;  //指向最小生成树的根节点
    int vertextnumber;
};

void MiniSpanTree_Prim(GraphAdjList g, MiniTree tree, int start_node) {
    tree.head = NULL;
    int *distance = (int*)malloc(sizeof(int) * g.vertexnumber + 2);
    int *miniadj = (int*)malloc(sizeof(int) * g.vertexnumber + 2);
    int i, j, k, lastnode, thisnode;
    lastnode = start_node;
    for(i=1; i<=g.vertexnumber; i++) {
        distance[i] = Biggest;
        miniadj[i] = i;
    }

    distance[start_node] = 0;
    tree.vertextnumber = 1;

    while(tree.vertextnumber < g.vertexnumber) {
        EdgeListNode *temp = g.vertextlist[lastnode].firstadj;
        while(temp != NULL) {
            j = temp->adjId;
            if(distance[j] && distance[j]>temp->weight) {
                distance[j] = temp->weight;
                miniadj[j] = lastnode;
            }
            temp = temp->next;
        }

        k = Biggest;
        for(i=1; i<=g.vertexnumber; i++) {
            if(distance[i] && k>distance[i]) {
                k = distance[i];
                thisnode = i;
            }
        }

        MiniTreeEdge *temp1 = (MiniTreeEdge*)malloc(sizeof(MiniTreeEdge));
        temp1->e = thisnode; //新加入的结点
        temp1->s = miniadj[thisnode]; //最小生成树中与新加入结点相连的结点
        temp1->weight = k; //新加入的边的权重
        temp1->next = NULL;
        temp1->next = tree.head;
        tree.head = temp1;
        distance[thisnode] = 0;

        lastnode = thisnode;
        tree.vertextnumber++;
    }

	//打印最小生成树
    MiniTreeEdge *e = tree.head;
    while(e != NULL) {
        cout<<e->s<<" -> "<<e->e<<"  :  "<<e->weight<<endl;
        e = e->next;
    }

}

  • 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
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
2.1.3 测试

测试的图为：
在这里插入图片描述

int main() {
    GraphAdjList g;
    g.edgenumber = 5;
    g.vertexnumber = 4;
    int i, j, k;
    EdgeListNode *temp;

    for(i=1; i<=4; i++) {
        g.vertextlist[i].data = i;
        g.vertextlist[i].firstadj = NULL;
    }

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 2; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 8; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 1; temp->weight = 2; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 3; temp->weight = 3; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 1; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 3; temp->next = g.vertextlist[3].firstadj;
    g.vertextlist[3].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 5; temp->next = g.vertextlist[3].firstadj;
    g.vertextlist[3].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 1; temp->weight = 8; temp->next = g.vertextlist[4].firstadj;
    g.vertextlist[4].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 1; temp->next = g.vertextlist[4].firstadj;
    g.vertextlist[4].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 3; temp->weight = 5; temp->next = g.vertextlist[4].firstadj;
    g.vertextlist[4].firstadj = temp;

    MiniTree tree;
    MiniSpanTree_Prim(g, tree, 1);
    MiniTreeEdge *e = tree.head;
    while(e != NULL) {
        cout<<e->s<<" -> "<<e->e<<"  :  "<<e->weight<<endl;
        e = e->next;
    }

    return 0;
}

  • 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

2.2 Kruskal算法

2.2.1 基本思想

假设现在要求无向连通图G=(V, E)的最小生成树T，Kruskal算法的思想是令T的初始状态为|V|个结点而无边的非连通图，T中的每个顶点自成一个连通分量。接着，每次从图G中所有两个端点落在不同连通分量的边中，选取权重最小的那条，将该边加入T中，如此往复，直至T中所有顶点都在同一个连通分量上。

注意
此处的关键点有两个：
（1）在生成最小生成树前，要对图中的所有边进行排序；
（2）如何判断一条边的两个端点是否落在不同的连通分量上：
这里可以用一个数组parent来记录每个端点在其所在连通图中的父端点（例如parent[i]表示端点i的父端点），在一个连通分量中，总有一个端点的父端点是它自己（把它看成是一棵树的根节点）。
1）开始的时候初始化该数组为parent[i]=i（因为每个端点所在的连通图只有自己）；
2）每次要判断一条边(u, v)的两个端点是否在在不同的连通分量上，就找端点u和端点v在它们所在的连通图中的最底层的父端点，具体的方法是递归地找端点k的父端点，直至某个端点的父端点等于它自己：

int find_parent(int node, int *parent) { //找端点node的最底层父端点
    while(parent[node] != node) {
        node = parent[node];
    }
    return node;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

3）假设n=find_parent(u, parent)，m=find_parent(v, parent)，那么就要对它们进行判断：
如果n==m，说明结点u和结点v在一个连通分量上，因此不能将其加入T；
如果n!=m，说明结点u和结点v不在一个连通分量上，这时可以将(u,v)加入T，且令parent[n]=m（或parent[m]=n）。

例子
仍然以上述这个无向连通图G为例，它有5个顶点，7条边，如下图所示。
在这里插入图片描述
利用Prim算法来生成该图的最小生成树T的过程如下：
（1）先对图中的所有边按照权重递增的顺序排序：
(A, C, 1) , (B, D, 2) , (B, E, 2) , (A, D , 4) , (A, E , 4) , (A, B, 6) , (C, D, 8).
对每个端点的parent进行初始化：
parent[A] = A, parent[B] = B, parent[C] = C, parent[D] = D, parent[E] = E.

（2）从权重最短的边开始遍历：
1）(A, C, 1)，因为parent[A] != parent[C]，所以将边(A, C)加入树T，且令parent[parent[C]]=parent[A]=A.此时，parent[A] = A, parent[B] = B, parent[C] = A, parent[D] = D, parent[E] = E，此时T中有1条边。

2）(B, D, 2)，因为parent[B] != parent[D]，将边(B, D)加入树T，且令parent[parent[D]]=parent[B]=B.此时，parent[A] = A, parent[B] = B, parent[C] = A, parent[D] = B, parent[E] = E，此时T中有2条边.

3）(B, E, 2)，因为parent[B] != parent[E]，将边(B, E)加入树T，且令parent[parent[E]]=parent[B]=B.此时，parent[A] = A, parent[B] = B, parent[C] = A, parent[D] = B, parent[E] = B，此时T中有3条边

4）(A, D, 2)，因为parent[A] != parent[D]，将边(A, D)加入树T，且令parent[parent[D]]=parent[A]=A.此时，parent[A] = A, parent[B] = A, parent[C] = A, parent[D] = B, parent[E] = E，此时T中有4条边，正好等于端点数减一，因此树T生成。

2.2.2 具体实现
#define Maximum 1000
#define Biggest 100000000

typedef struct EdgeListNode{
    int adjId;
    int weight;
    EdgeListNode* next;
};

typedef struct VertexListNode{
    int data;
    EdgeListNode* firstadj;
};

typedef struct GraphAdjList{
    int vertexnumber;
    int edgenumber;
    VertexListNode vertextlist[Maximum];
};

typedef struct MiniTreeEdge {
    int s;
    int e;
    int weight;
    MiniTreeEdge *next;
};

typedef struct MiniTree {
    MiniTreeEdge *head;
    int edgenumber;
};

typedef struct EdgeArrayData {
    int l;
    int r;
    int weight;
};

bool compare(EdgeArrayData a, EdgeArrayData b) {
    return a.weight < b.weight;
}

int find_parent(int node, int *parent) {
    while(parent[node] != node) {
        node = parent[node];
    }
    return node;
}

void  MiniSpanTree_Kruskal(GraphAdjList g, MiniTree *tree) {
    int i, j, k, edge_index, *parent;
    MiniTreeEdge *e;
    EdgeArrayData *edge = (EdgeArrayData*)malloc(sizeof(EdgeArrayData)*(g.edgenumber+2));
    parent = (int*)malloc(sizeof(int)*(g.vertexnumber+2));
    tree = (MiniTree*)malloc(sizeof(MiniTree));
    EdgeListNode *v;

	//将图中的每条边存储在edge里
    edge_index = 0;
    for(i=1; i<=g.vertexnumber; i++) {
        v = g.vertextlist[i].firstadj;
        parent[i] = i;
        while(v != NULL) {
            if(v->adjId > i) {  //为了避免将一条边存两次
                edge[edge_index].l = i;
                edge[edge_index].r = v->adjId;
                edge[edge_index].weight = v->weight;
                edge_index++;
            }
            v = v->next;
        }
    }
    sort(edge, edge+edge_index, compare); //将边按权重从小到大排序
    
    tree->edgenumber = 0;
    tree->head = NULL;
    for(i=0; i<edge_index; i++) {
        j = find_parent(edge[i].l, parent); 
        k = find_parent(edge[i].r, parent);
        if(j != k) {
            parent[j] = k;
            e = (MiniTreeEdge*)malloc(sizeof(MiniTreeEdge));
            e->s = edge[i].l;
            e->e = edge[i].r;
            e->weight = edge[i].weight;
            e->next = tree->head;
            tree->head = e;
            tree->edgenumber++;
        }
        if(tree->edgenumber == g.vertexnumber - 1) {
            break;
        }
    }

    MiniTreeEdge *ee = tree->head;
    while(ee != NULL) {
        cout<<ee->s<<" -> "<<ee->e<<"  :  "<<ee->weight<<endl;
        ee = ee->next;
    }
}

  • 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
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
2.2.3 测试

测试的图为：
在这里插入图片描述


int main() {
    GraphAdjList g;
    g.edgenumber = 5;
    g.vertexnumber = 4;
    int i, j, k;
    EdgeListNode *temp;

    for(i=1; i<=4; i++) {
        g.vertextlist[i].data = i;
        g.vertextlist[i].firstadj = NULL;
    }

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 2; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 8; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 1; temp->weight = 2; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 3; temp->weight = 3; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 1; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 3; temp->next = g.vertextlist[3].firstadj;
    g.vertextlist[3].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 5; temp->next = g.vertextlist[3].firstadj;
    g.vertextlist[3].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 1; temp->weight = 8; temp->next = g.vertextlist[4].firstadj;
    g.vertextlist[4].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 1; temp->next = g.vertextlist[4].firstadj;
    g.vertextlist[4].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 3; temp->weight = 5; temp->next = g.vertextlist[4].firstadj;
    g.vertextlist[4].firstadj = temp;

    MiniTree *tree;
    MiniSpanTree_Kruskal(g, tree);
    MiniTreeEdge *e = tree->head;
    while(e != NULL) {
        cout<<e->s<<" -> "<<e->e<<"  :  "<<e->weight<<endl;
        e = e->next;
    }

    return 0;
}

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/243400
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号