图的应用——最小生成树

野性酷女 2021-11-16 15:10 296阅读 0赞

最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。  
最小生成树可以用Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法求出。

我们将以下面的带权连通图为例讲解这两种算法的实现：  
![带权连通图][SouthEast]

--------------------

**Prim（普里姆）算法**  
时间复杂度：O（N^2）（N为顶点数）  
prim算法又称“**加点法**”，用于边数较多的带权无向连通图  
方法：每次找与之连线权值最小的顶点，将该点加入最小生成树集合中  
注意：相同权值任选其中一个即可，但是**不允许出现闭合回路**的情况。  
![1][]  
![2][]  
![3][]  
![4][]  
![5][]  
![6][]  
![7][]

代码部分通过以下步骤可以得到最小生成树：

1.初始化：  
lowcost\[i\]:表示以i为终点的边的最小权值,当lowcost\[i\]=0表示i点加入了VEST。

vest\[i\]:表示对应lowcost\[i\]的起点，当vest\[i\]=0表示起点i加入VEST。  
**由于我们规定最开始的顶点是1，所以lowcost\[1\]=0，VEST\[1\]=0。即只需要对2~n进行初始化即可。**

**实现结果：**

**范例输入：**

**6 9  
0 1 2 3 4 5  
0 1 6  
0 2 1  
0 3 5  
1 2 5  
1 4 3  
2 3 5  
2 4 6  
2 5 4  
3 5 2**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

**代码：**

void prim(AMGraph G,int v,int &sum)         //prim创建最小生成树
    {
        int lowcost[MaxSize],vest[MaxSize],v1;
        int i,j,k,min;
        v1 = v;
        for(i=0;i<G.n;i++)
        {
            lowcost[i] = G.arcs[v1][i];         //lowcost保存与v连接的各顶点的权值，与v未连接的置为INF
            vest[i] = 0;                        //vest数组初始化表示当前集合无顶点
        }
        vest[v] = 1;                            //将v顶点加入集合
        sum = 0;
        for(i=0;i<G.n-1;i++)                    //对剩下的n-1个顶点进行访问
        {
            min = INF;
            for(j=0;j<G.n;j++)                  //选出与v连接的权值最小的顶点
            {
                if(vest[j]==0&&lowcost[j]<min)
                {
                    min = lowcost[j];
                    k = j;
                }
            }
            vest[k] = 1;
            v1 = k;
            sum+=min;
            for(j=0;j<G.n;j++)                  //更新lowcost数组
            {
                if(vest[j]==0&&G.arcs[v1][j]<lowcost[j])  //生成树（树这一整体）到剩余各顶点最短边的权值
                    lowcost[j] = G.arcs[v1][j];
            }
        }
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    #define MaxSize 20
    #define INF 100
    typedef struct
    {
        int vexs[MaxVertices];
        int arcs[MaxVertices][MaxVertices];
        int n,e;
    }AMGraph;
    void CreateGraph(AMGraph &G)           //生成邻接矩阵
    {
        int i,j,w,vi,vj;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&G.n,&G.e);
        printf("创建顶点表:\n");
        for(i=0;i<G.n;i++)
        {
             scanf("%d",&G.vexs[i]);
        }
        for(i=0;i<G.n;i++)
        {
             for(j=0;j<G.n;j++)
             {
                 G.arcs[i][j] = INF;
             }
    
        }
        printf("创建边表:\n");
        for(i=0;i<G.e;i++)
        {
            scanf("%d %d %d",&vi,&vj,&w);
            G.arcs[vi][vj] = w;
            G.arcs[vj][vi] = w;
        }
    }
    void prim(AMGraph G,int v,int &sum)         //prim创建最小生成树
    {
        int lowcost[MaxSize],vest[MaxSize],v1;
        int i,j,k,min;
        v1 = v;
        for(i=0;i<G.n;i++)
        {
            lowcost[i] = G.arcs[v1][i];         //lowcost保存与v连接的各顶点的权值，与v未连接的置为INF
            vest[i] = 0;                        //vest数组初始化表示当前集合无顶点
        }
        vest[v] = 1;                            //将v顶点加入集合
        sum = 0;
        for(i=0;i<G.n-1;i++)                    //对剩下的n-1个顶点进行访问
        {
            min = INF;
            for(j=0;j<G.n;j++)                  //选出与v连接的权值最小的顶点
            {
                if(vest[j]==0&&lowcost[j]<min)
                {
                    min = lowcost[j];
                    k = j;
                }
            }
            vest[k] = 1;
            v1 = k;
            sum+=min;
            for(j=0;j<G.n;j++)                  //更新lowcost数组
            {
                if(vest[j]==0&&G.arcs[v1][j]<lowcost[j])  //生成树（树这一整体）到剩余各顶点最短边的权值
                    lowcost[j] = G.arcs[v1][j];
            }
        }
    }
    int main()
    {
        int sum;
        AMGraph G;
        CreateGraph(G);
        prim(G,0,sum);
        printf("最小生成树权值和为:%d\n",sum);
    }

**kruskal（克鲁斯卡尔）算法**  
时间复杂度：O（NlogN）（N为边数）  
kruskal算法又称“**加边法**”，用于边数较少的稀疏图  
方法：每次找图中权值最小的边，将边连接的两个顶点加入最小生成树集合中  
注意：相同权值任选其中一个即可，但是**不允许出现闭合回路**的情况。  
![1][1 1]  
![2][2 1]  
![3][3 1]  
![4][4 1]  
![5][5 1]  
![6][6 1]  
代码部分通过以下步骤可以得到最小生成树：

**1.初始化：  
构建边的结构体，包括起始顶点、终止顶点，边的权值  
借用一个辅助数组vset\[i\]用来判断某边是否加入了最小生成树集合**

**运行结果：**

**范例输入：**

**6 9  
1 2 3 4 5 6  
1 2 6  
1 3 1  
1 4 5  
2 3 5  
2 5 3  
3 4 5  
3 5 6  
3 6 4  
4 6 2**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

int getRoot(int a)      //在并查集中查找根节点
    {
        while(a != v[a])
            a = v[a];
        return a;
    }
    void kruskal(AdjList *G,int &sum,Road road[])
    {
        int i;
        int N,E,a,b;
        N = G->n;
        E = G->e;
        sum = 0;
        for(i=0;i<N;i++) v[i] = i;          //并查集数组初始化为顶点序号
        sort(road,E);
        for(i=0;i<E;i++)
        {
            a = getRoot(road[i].v);
            b = getRoot(road[i].x);
            if(a!=b)
            {
                v[a] = b;
                sum+=road[i].w;
            }
        }
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    #define MaxSize 20
    typedef struct node
    {
        int adjvex;
        node* next;
    }ArcNode;
    typedef struct
    {
        int data;
        ArcNode* first;
    }VerNode;
    typedef struct
    {
        VerNode adjList[MaxVertices];
        int n,e;
    }AdjList;
    typedef struct
    {
        int v,x;            //v,x为一条边所连的两个顶点
        int w;              //边的权值
    }Road;  
    Road road[MaxSize];
    int v[MaxSize];
    void CreateGraph(AdjList *G)
    {
        int i,a,b,w;
        ArcNode *s;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&G->n,&G->e);
        printf("创建顶点表:\n");
        for(i=0;i<G->n;i++)
        {
            scanf("%d",&G->adjList[i].data);
            G->adjList[i].first = NULL;
        }
        printf("创建边表:\n");
        for(i=0;i<G->e;i++)
        {
            scanf("%d %d %d",&a,&b,&w);
            road[i].v = a;              
            road[i].x = b;
            road[i].w = w;
            
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = b;
            s->next = G->adjList[a].first;
            G->adjList[a].first = s;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = a;
            s->next = G->adjList[b].first;
            G->adjList[b].first = s;
        }
    }
    void sort(Road road[],int E)           //权值排序，采用冒泡排序
    {
        int i,j,temp,temp1,temp2;
        for(i=0;i<E;i++)
        {
            for(j=0;j<E-i-1;j++)
            {
                if(road[j].w > road[j+1].w)
                {
                    temp1 = road[j+1].v;
                    temp2 = road[j+1].x;
                    temp = road[j+1].w;
    
                    road[j+1].v = road[j].v;
                    road[j].v = temp1;
    
                    road[j+1].x = road[j].x;
                    road[j].x = temp2;
    
                    road[j+1].w = road[j].w;
                    road[j].w = temp;
                }
            }
        }
    }
    int getRoot(int a)      //在并查集中查找根节点
    {
        while(a != v[a])
            a = v[a];
        return a;
    }
    void kruskal(AdjList *G,int &sum,Road road[])
    {
        int i;
        int N,E,a,b;
        N = G->n;
        E = G->e;
        sum = 0;
        for(i=0;i<N;i++) v[i] = i;          //并查集数组初始化为顶点序号
        sort(road,E);
        for(i=0;i<E;i++)
        {
            a = getRoot(road[i].v);
            b = getRoot(road[i].x);
            if(a!=b)
            {
                v[a] = b;
                sum+=road[i].w;
            }
        }
    }
    int main()
    {
        int sum;
        AdjList *G = (AdjList*)malloc(sizeof(AdjList));
        CreateGraph(G);
        kruskal(G,sum,road);
        printf("最小生成树:%d\n",sum);
    }

[SouthEast]: /images/20211116/e8acbf2462f34b51ad86243584959937.png
[1]: /images/20211116/d135bc6fee8c4eccb87fc156217df87a.png
[2]: /images/20211116/f030f2b649e24157a8b6437ed8795c1d.png
[3]: /images/20211116/b78eb13ddc244fcd8f65487ea4e676e1.png
[4]: /images/20211116/bbc1127ad57149348b56dd929bd51f03.png
[5]: /images/20211116/1348ff792e384993b061f0c85f83f8ec.png
[6]: /images/20211116/1eb12155a4f04095b04c6179bcf85a07.png
[7]: /images/20211116/51ceb2026e624c97aecaf2df7e641959.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211116/7c616144fde144d9a6c6f9cc78357f2f.png
[1 1]: /images/20211116/d52dc38a334d4818981ec6ca566998a6.png
[2 1]: /images/20211116/06929e0a303e484d9c375c754ce728ff.png
[3 1]: /images/20211116/0ebfee59c0de4877869d610b9144e792.png
[4 1]: /images/20211116/c58a237cdddc4363abb2b775978030e3.png
[5 1]: /images/20211116/c77ba5790420475d898334935d21499a.png
[6 1]: /images/20211116/6a7eeb32776d42fb8f7fdca03c79debd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20211116/ca303003e9324dfb98d87d00df7d8714.png