最小生成树

假设要在 $n$ 个城市之间建立通信联络网,则连通 $n$ 个城市只需要 $n-1$条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价。$n$个城市之间,最多可能设置 $n(n-1)/2$条线路,那么,如何在这些可能的线路中选择 $n-1$条,以使总的耗费最少呢?

可以用连通网来表示 $n$ 个城市以及 $n$ 个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于 $n$ 个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树( Minimum Cost Spanning Tree )(简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。

构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为 $MST$ 的性质:假设 $N$=( $V$ , { $E$ })是一个连通网, U 是顶点集 V 的一个非空子集。若$(u,v)$是一条具有最小权值(代价)的边,其中 $u\in U,v\in V-U$ ,则必存在一棵包含边$(u,v)$的最小生成树。

可以用反证法证明之。假设网 $N$ 的任何一棵最小生成树都不包含$(u,v)$。设 $T$是连通网上的一棵最小生成树,当将边$(u,v)$加人到 $T$ 中时,由生成树的定义, $T$ 中必存在一条包含$(u,v)$的回路。另一方面,由于 $T$ 是生成树,则在 $T$ 上必存在另一条边$(u^{\prime },v^{\prime })$,其中 $u\in U$ , $v\in V-U$ ,且 $u$ 和 $u^{\prime }$ 之间, $v$ 和 $v^{\prime }$ 之间均有路径相通。删去边$(u,v)$,便可消除上述回路,同时得到另一棵生成树 $T^{\prime }$ 。因为$(u,v)$的代价不高于$(u^{\prime },v^{\prime })$,则 $T^{\prime }$ 的代价亦不高于 $T$ , $T^{\prime }$ 是包含$(u,v)$的一棵最小生成树。由此和假设矛盾。

普里姆( Prim )算法和克鲁斯卡尔( Kruskal )算法是两个利用 MST 性质构造最小生成树的算法。

普里姆算法

假设 $N$=( $V$,{ $E$} )是连通网, $TE$ 是 $N$ 上最小生成树中边的集合。算法从 $U$ ={ $u_o$ }$(u_o\in V)$ , $TE$ ={ }开始,重复执行下述操作:在所有 $u\in U,v\in V-U$ 的边$(u,v)\in E$ 中找一条代价最小的边$(u_o,v_o)$并人集合 $TE$ ,同时并人 $U$ ,直至 $U=V$ 为止。此时 $TE$ 中必有 $n-1$条边,则 $T$ =( $V$ , { $TE$} )为 $N$ 的最小生成树。

为实现这个算法需附设一个辅助数组 $closedge$ ,以记录从 $U$ 到 $V-U$ 具有最小代价的边。对每个顶点 $u_i\in V-U$ ,在辅助数组中存在一个相应分量 $closedge[i—1]$,它包括两个域,其中 $lowcost$ 存储该边上的权。显然,
$closedge[i-1]$. $lowcost$ = Min { cost { $u,v_i$} | $u\in U$ }

$vex$ 域存储该边依附的在 $U$ 中的顶点。例如,图7.16所示为按普里姆算法构造网的一棵最小生成树的过程,在构造过程中辅助数组中各分量值的变化如图7.17所示。初始状态

时,由于 $U$ =( $v_1$ ),则到 $V-U$ 中各顶点的最小边,即为从依附于顶点1的各条边中,找到一条代价最小的边$(u_o,v_o)=(1,3)$为生成树上的第一条边,同时将 $u_o(=u_3)$并人集合 $U$ 。然后修改辅助数组中的值。首先将 $closedge[2]$. $lowcost$ 改为’0’,以示顶点 $v_3$ 已并入 $U$ 。

然后,由于边$(v_3,v_2)$上的权值小于 $closedge[1]$. $lowcost$ ,则需修改 $closedge[1]$为边$(v_3,v_2)$及其权值。同理修改 $closedge[4]$和 $closedge[5]$。依次类推,直到 $U=V$ 。假设以二维数组表示网的邻接矩阵,且令两个顶点之间不存在的边的权值为机内允许的最大值( $INT$_$MAX$ ),则普里姆算法如算法7.9所示。

#include <bits/stdc++.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

#define INFINITY 65535 //最大值∞
#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef int VertexType;
typedef enum
{
   
    DG,
    DN,
    UDG,
    UDN
} GraphKind; //{有向图，有向网，无向图，无向网}

typedef struct ArcCell
{
   
    VRType adj;     //VRType 是顶点关系类型。对无权图，用0或1表示相邻否；对带权图，则为权值类型
    InfoType *info; //该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
   
    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs;                  //邻接矩阵
    int vexnum, arcnum;              //图的当前顶点数和弧数
    GraphKind kind;                  //图的种类标志
} MGraph;

typedef struct
{
   
    VertexType adjvex;
    VRType lowcost;
} CLOSEDGE;

/*******************************声明部分****************************************/
Status CreateUDN(MGraph *G);
//构造无向网
int LocateVex(MGraph G, VertexType v);
//确定v在G中的位置
int minimum(CLOSEDGE closedge[], int n);
//返回最小连接的顶点序号
void MiniSpanTree_PRIM(MGraph G, VertexType u);
//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
//记录从顶点集U到V-U的代价最小的边的辅助数组定义
/*******************************函数部分****************************************/
Status CreateUDN(MGraph *G)
{
   
    printf("\n构造无向网\n");
    int i, j, k;       //i,j,k用于计数
    int w;             //权重
    VertexType v1, v2; //弧头，弧尾

    printf("请输入顶点个数：");
    scanf("%d", &(*G).vexnum);
    printf("请输入弧个数：");
    scanf("%d", &(*G).arcnum);
    //假定该图不含其他信息
    int IncInfo = 0;

    for (i = 0; i < (*G).vexnum; i++)
    {
    //构造顶点向量
        printf("请输入G.vexs[%d] = ", i);
        scanf("%d", &(*G).vexs[i]);
    } //for

    for (i = 0; i < (*G).vexnum; i++) //初始化邻接矩阵
        for (j = 0; j < (*G).vexnum; j++)
        {
   
            (*G).arcs[i][j].adj = INFINITY; //无向网
            (*G).arcs[i][j].info = NULL;
        }

    for (k = 0; k < (*G).arcnum; k++)
    {
                                      //构造邻接矩阵
        printf("请输入弧头(初始点)："); //输入一条弧的始点和终点
        scanf("%d", &v1);
        printf("请输入弧尾(终端点)：");
        scanf("%d", &v2);
        printf("请输入权重：");
        scanf("%d", &w);

        i = LocateVex(*G, v1);
        j = LocateVex(*G, v2);

        if (i >= 0 && j >= 0)
            (*G).arcs[i][j].adj = (*G).arcs[j][i].adj = w; //置<v1,v2>的对称弧<v2,v1>

        //不再输入该弧含有的相关信息
    }
    (*G).kind = UDN;
    return OK;
}

int LocateVex(MGraph G, VertexType v)
{
   
    int ct;
    for (ct = 0; ct < G.vexnum; ct++)
        if (G.vexs[ct] == v)
            return ct;
    return -1;
}

int minimum(CLOSEDGE closedge[], int n)
{
   
    int i = 0, j, min, k;
    while (!closedge[i].lowcost)
        i++;
    min = closedge[i].lowcost;
    k = i;
    for (j = 1; j < n; j++)
        if (closedge[j].lowcost)
            if (min > closedge[j].lowcost)
            {
   
                min = closedge[j].lowcost;
                k = j;
            } //if
    return k;
}

void MiniSpanTree_PRIM(MGraph G, VertexType u)
{
   
    CLOSEDGE closedge[G.vexnum + 1];
    int k, j, i;

    k = LocateVex(G, u);
    for (j = 0; j < G.vexnum; ++j)
        if (j != k)
        {
    //辅助数组初始化
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j].adj;
        } //if

    closedge[k].lowcost = 0; //初始，U = {u}
    for (i = 1; i < G.vexnum; ++i)
    {
    //选择其余G.vexnum-1个顶点

        k = minimum(closedge, G.vexnum);                    //求出T的下一个结点：第k个顶点
        printf("(%d,%d)\n", closedge[k].adjvex, G.vexs[k]); //输出生成树的边

        closedge[k].lowcost = 0; //第k顶点并入U集

        for (j = 0; j < G.vexnum; ++j)
        {
   
            if (G.arcs[k][j].adj < closedge[j].lowcost)
            {
    //新顶点并入U集后重新选择最小边
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j].adj;
            } //if
        }     //for
    }         //for
}

/*******************************主函数部分**************************************/

int main()
{
   
    MGraph G;
    printf("P174 图7.16（a）\n");
    CreateUDN(&G);
    printf("\n输出生成树上的5条边为：\n");
    MiniSpanTree_PRIM(G, 1);
    return 0;
}

克鲁斯卡尔

例如,对图7.16( a )中的网,利用算法7.9,将输出生成树上的5条边为:{ $(v_1,v_3),(v_3,v_6),(v_6,v_4),(v_3,v_2).(v_2,v_5)$ }。

分析算法7.9,假设网中有 $n$ 个顶点,则第一个进行初始化的循环语句的频度为 $n$ ,第二个循环语句的频度为 $n-1$。其中有两个内循环:其一是在 $closedge[v]$. $lowcost$ 中求最小值,其频度为 $n-1$;其二是重新选择具有最小代价的边,其频度为 $n$ 。由此,普里姆算法的时间复杂度为 $O(n)$,与网中的边数无关,因此适用于求边稠密的网的最小生成树。

而克鲁斯卡尔算法恰恰相反,它的时间复杂度为 $O(eloge)$( $e$ 为网中边的数目),因此它相对于普里姆算法而言,适合于求边稀疏的网的最小生成树。

克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网 $N$ =( $V$ , { $E$ } ),则令最小生成树的初始状态为只有 $n$个顶点而无边的非连通图 $T$ =( $V$ , { } ),图中每个顶点自成一个连通分量。在 $E$ 中选择代价最小的边,若该边依附的顶点落在 $T$ 中不同的连通分量上,则将此边加人到 $T$ 中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。

例如,图7.18所示为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为

1,2,3,4的4条边由于满足上述条件,则先后被加人到 $T$ 中,代价为5的两条边$(v_1,v_4)$和$(v_3,v_4)$被舍去。因为它们依附的两顶点在同一连通分量上,它们若加人 T 中,则会使 T 中产生回路,而下一条代价$(=5)$最小的边$(v_2,v_3)$联结两个连通分量,则可加人 $T$ 。由此,构造成一棵最小生成树。

上述算法至多对 $e$ 条边各扫描一次,假若以第9章将介绍的“堆”来存放网中的边,则每次选择最小代价的边仅需 $O(loge)$的时间( 第一次需 $O(e)$ )。又生成树 T 的每个连通分量可看成是一个等价类,则构造 $T$ 加人新的边的过程类似于求等价类的过程,由此可以以6.5节中介绍的 $MFSet$ 类型来描述 $T$ ,使构造 T 的过程仅需 $O(eloge)$的时间,由此,克鲁斯卡尔算法的时间复杂度为 $O(eloge)$。

#include<bits/stdc++.h>
using namespace std;
//hdu 1233 kruskal+并查集
const int NUM = 100;
int s[NUM]; //并查集
struct Edge{
   
    int u, v, w;
} edge[NUM * NUM];  //定义边
bool cmp(Edge a,Edge b){
   
    return a.w < b.w;
}
int find(int u){
   
    return s[u] == u ? u : find(s[u]);
}

int n, m;
int kruskal(){
   
    int ans = 0;
    for (int i = 1; i <= n; i++)
        s[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1; i <= n;i++){
   
        int b = find(edge[i].u);
        int c = find(edge[i].v);
        if(b==c)
            continue;
        s[c] = b;
        ans += edge[i].w;
    }
    return ans;
}

int main(){
   
    while(cin>>n){
   
        m = n * (n - 1) / 2;
        for (int i = 1; i <= m;i++){
   
            cin >> edge[i].u >> edge[i].v >> edge[i].w;
        }
        cout << kruskal() << endl;
    }
    return 0;
}

更多数据结构代码实现请关注我的专栏数据结构

或者进入2021-10-16【严蔚敏数据结构代码实现合集】【c语言学习必备】学习