文档章节

数据结构之 最小生成树

小竹zz
 小竹zz
发布于 2014/09/10 12:53
字数 2948
阅读 33
收藏 0

 一个连通图的生成树是一个极小的连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。

    找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。下面分别介绍两种算法。

一、普里姆(Prim)算法

    普里姆算法,图论中的一种算法,可在加权连通图里搜索最小生成树。意即此算法搜索到的边子集所构成的树中,不但包括连通图里的所有顶点,且其所有边的权值之和亦为最小。

1.1 算法描述

    从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
    (1)输入:一个加权连通图,其中顶点集合为V,边集合为E;
    (2)初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {};
    (3)重复下列操作,直到Vnew = V:
            在集合E中选取权值最小的边(u, v),其中u为集合Vnew中的元素,而v则不是(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
            将v加入集合Vnew中,将(u, v)加入集合Enew中;
    (4)输出:使用集合VnewEnew来描述所得到的最小生成树。

1.2 例示

      

      

1.3 普里姆算法实现

/* 邻接矩阵表示的图结构*/
#include <stdio.h>
#include <stdlib.h>
#include <curses.h>
 
typedefchar VertexType;        //顶点类型应由用户定义
typedefint EdgeType;           //边上的权值类型应由用户定义
 
#define MAXVEX  100             //最大顶点数,应由用户定义
#define INFINITY    65535       //用65535来代表无穷大
#define DEBUG
 
//邻接矩阵结构
typedefstruct
{
    VertexType vexs[MAXVEX];    //顶点表
    EdgeType   arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边
    intnumVertexes, numEdges;      //图中当前的顶点数和边数
}Graph;
 
//定位
intlocates(Graph *g, charch)
{
    inti = 0;
    for(i = 0; i < g->numVertexes; i++)
    {
        if(g->vexs[i] == ch)
        {
            break;
        }
    }
    if(i >= g->numVertexes)
    {
        return-1;
    }
     
    returni;
}
 
//建立一个无向网图的邻接矩阵表示
voidCreateGraph(Graph *g)
{
    inti, j, k, w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
     
    #ifdef DEBUG
    printf("%d %d\n", g->numVertexes, g->numEdges);
    #endif
 
    for(i = 0; i < g->numVertexes; i++)
    {
        printf("请输入顶点%d:\n", i);
        g->vexs[i] = getchar();
        while(g->vexs[i] == '\n')
        {
            g->vexs[i] = getchar();
        }
    }
     
    #ifdef DEBUG
    for(i = 0; i < g->numVertexes; i++)
    {
        printf("%c ", g->vexs[i]);
    }
    printf("\n");
    #endif
 
 
    for(i = 0; i < g->numEdges; i++)
    {
        for(j = 0; j < g->numEdges; j++)
        {
            g->arc[i][j] = INFINITY; //邻接矩阵初始化
        }
    }
    for(k = 0; k < g->numEdges; k++)
    {
        charp, q;
        printf("输入边(vi,vj)上的下标i,下标j和权值:\n");
         
        p = getchar();
        while(p == '\n')
        {
            p = getchar();
        }
        q = getchar();
        while(q == '\n')
        {
            q = getchar();
        }
        scanf("%d", &w);    
         
        intm = -1;
        intn = -1;
        m = locates(g, p);
        n = locates(g, q);
        if(n == -1 || m == -1)
        {
            fprintf(stderr,"there is no this vertex.\n");
            return;
        }
        //getchar();
        g->arc[m][n] = w;
        g->arc[n][m] = g->arc[m][n];  //因为是无向图,矩阵对称
    }
}
 
//打印图
voidprintGraph(Graph g)
{
    inti, j;
    printf("构建的邻接矩阵如下所示.\n");
    for(i = 0; i < g.numVertexes; i++)
    {
        for(j = 0; j < g.numVertexes; j++)
        {
            printf("%5d  ", g.arc[i][j]);
        }
        printf("\n");
    }
}
 
//prime算法最小生成树
voidMiniSpanTree_Prime(Graph g)
{
    intmin, i, j, k;
    intadjvex[MAXVEX];         //保存相关顶点下标
    intlowcost[MAXVEX];        //保存相关顶点间边的权值
    lowcost[0] = 0;             //初始化第一个权值为0,即v0加入生成树
 
    adjvex[0] = 0;              //初始化第一个顶点下标为0
    for(i = 1; i < g.numVertexes; i++)
    {
        //循环除下标为0外的全部顶点
        lowcost[i] = g.arc[0][i];   //将v0顶点与之有边的权值存入数组
        adjvex[i] = 0;              //初始化都为v0下标
    }
    for(i = 1; i < g.numVertexes; i++)
    {
        min = INFINITY;             //初始化最小权值为无穷大
        j = 1;
        k = 0;
        while(j < g.numVertexes) //循环全部顶点
        {
            //如果权值不为0,且权值小于min
            if(lowcost[j] != 0 && lowcost[j] < min)
            {
                min = lowcost[j];       //则让当前权值成为最小值
                k = j;                  //将当前最小值的下标存入k
            }
            j++;
        }
        printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边
        lowcost[k] = 0;                 //将当前顶点的权值设置为0,表示此顶点已经完成任务
 
        for(j = 1; j < g.numVertexes; j++)//循环所有顶点
        {
            if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j])
            {
                //若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
                lowcost[j] = g.arc[k][j];
                adjvex[j] = k;              //将下标为k的顶点存入adjvex
            }
        }
    }
    printf("\n");
}
 
intmain(intargc, char**argv)
{
    Graph g;
     
    //邻接矩阵创建图
    CreateGraph(&g);
    //打印网图
    printGraph(g);
    //求最小生成树
    MiniSpanTree_Prime(g);
 
    return0;
}


      运行结果如下:

    

    

    

    由代码实现可知,邻接矩阵实现的普里姆算法的时间复杂度为O(n2)。


二、克鲁斯卡尔(Kruskal)算法

    普力马算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路,我们也可以直接就以边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。此时,我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码:

1
2
3
4
5
6
7
//对边集数组Edge结构的定义
  typedef struct
   {
       int begin;
       int end;
      int weight;
  }Edge;
      我们可以通过程序将邻接矩阵通过程序转化为边集数组,并且对它们的按权值从小到大排序。如下图所示。

    

    于是克鲁斯卡尔算法代码如下,左侧数字为行号。其中MAXEDGE为边数量的最大值,MAXVEX为顶点个数最大值。具体代码如下所示。

/* 邻接矩阵表示的图结构*/
#include <stdio.h>
#include <stdlib.h>
 
 
typedefchar VertexType;        //顶点类型应由用户定义
typedefint EdgeType;           //边上的权值类型应由用户定义
 
#define MAXVEX  100             //最大顶点数,应由用户定义
#define INFINITY    65535       //用65535来代表无穷大
#define DEBUG
 
//邻接矩阵结构
typedefstruct
{
    VertexType vexs[MAXVEX];    //顶点表
    EdgeType   arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边
    intnumVertexes, numEdges;      //图中当前的顶点数和边数
}Graph;
 
//边集数组
#define MAXEDGE   100
typedefstruct
{
    intbegin;
    intend;
    intweight;
}Edge;
 
 
 
//定位
intlocates(Graph *g, charch)
{
    inti = 0;
    for(i = 0; i < g->numVertexes; i++)
    {
        if(g->vexs[i] == ch)
        {
            break;
        }
    }
    if(i >= g->numVertexes)
    {
        return-1;
    }
     
    returni;
}
 
//建立一个无向网图的邻接矩阵表示
voidCreateGraph(Graph *g)
{
    inti, j, k, w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
     
    #ifdef DEBUG
    printf("%d %d\n", g->numVertexes, g->numEdges);
    #endif
 
    for(i = 0; i < g->numVertexes; i++)
    {
        printf("请输入顶点%d:\n", i);
        g->vexs[i] = getchar();
        while(g->vexs[i] == '\n')
        {
            g->vexs[i] = getchar();
        }
    }
     
    #ifdef DEBUG
    for(i = 0; i < g->numVertexes; i++)
    {
        printf("%c ", g->vexs[i]);
    }
    printf("\n");
    #endif
 
 
    for(i = 0; i < g->numEdges; i++)
    {
        for(j = 0; j < g->numEdges; j++)
        {
            g->arc[i][j] = INFINITY; //邻接矩阵初始化
        }
    }
    for(k = 0; k < g->numEdges; k++)
    {
        charp, q;
        printf("输入边(vi,vj)上的下标i,下标j和权值:\n");
         
        p = getchar();
        while(p == '\n')
        {
            p = getchar();
        }
        q = getchar();
        while(q == '\n')
        {
            q = getchar();
        }
        scanf("%d", &w);    
         
        intm = -1;
        intn = -1;
        m = locates(g, p);
        n = locates(g, q);
        if(n == -1 || m == -1)
        {
            fprintf(stderr,"there is no this vertex.\n");
            return;
        }
        //getchar();
        g->arc[m][n] = w;
        g->arc[n][m] = g->arc[m][n];  //因为是无向图,矩阵对称
    }
}
 
//打印图
voidprintGraph(Graph g)
{
    inti, j;
    printf("构建的邻接矩阵如下所示.\n");
    for(i = 0; i < g.numVertexes; i++)
    {
        for(j = 0; j < g.numVertexes; j++)
        {
            printf("%5d  ", g.arc[i][j]);
        }
        printf("\n");
    }
}
 
//prime算法最小生成树
voidMiniSpanTree_Prime(Graph g)
{
    intmin, i, j, k;
    intadjvex[MAXVEX];         //保存相关顶点下标
    intlowcost[MAXVEX];        //保存相关顶点间边的权值
    lowcost[0] = 0;             //初始化第一个权值为0,即v0加入生成树
 
    adjvex[0] = 0;              //初始化第一个顶点下标为0
    for(i = 1; i < g.numVertexes; i++)
    {
        //循环除下标为0外的全部顶点
        lowcost[i] = g.arc[0][i];   //将v0顶点与之有边的权值存入数组
        adjvex[i] = 0;              //初始化都为v0下标
    }
    for(i = 1; i < g.numVertexes; i++)
    {
        min = INFINITY;             //初始化最小权值为无穷大
        j = 1;
        k = 0;
        while(j < g.numVertexes) //循环全部顶点
        {
            //如果权值不为0,且权值小于min
            if(lowcost[j] != 0 && lowcost[j] < min)
            {
                min = lowcost[j];       //则让当前权值成为最小值
                k = j;                  //将当前最小值的下标存入k
            }
            j++;
        }
        printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边
        lowcost[k] = 0;                 //将当前顶点的权值设置为0,表示此顶点已经完成任务
 
        for(j = 1; j < g.numVertexes; j++)//循环所有顶点
        {
            if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j])
            {
                //若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
                lowcost[j] = g.arc[k][j];
                adjvex[j] = k;              //将下标为k的顶点存入adjvex
            }
        }
    }
    printf("\n");
}
 
//查找连线顶点的尾部
intFind(int*parent, intf)
{
    while(parent[f] > 0)
    {
        f = parent[f];
    }
    returnf;
}
 
//直接插入排序
voidInsertSort(Edge edges[], intk)
{
    inti, j;
    Edge ss;
    for(i = 1; i <= k; i++)
    {
        if(edges[i].weight < edges[i - 1].weight)
        {
            ss = edges[i];
            for(j = i - 1; edges[j].weight > ss.weight; j--)
            {
                edges[j + 1] = edges[j];
            }
            edges[j + 1] = ss;
        }
    }
}
 
 
//将邻接矩阵转化为边集数组
voidConvert(Graph g, Edge edges[])
{
    inti;
    intj;
    intk;
     
    k = 0;
    for(i = 0; i < g.numVertexes; i++)
    {
        for(j = i; j < g.numVertexes; j++)
        {
            if(g.arc[i][j] < 65535)
            {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = g.arc[i][j];
                k++;
            }
        }
    }
    k--;
 
#ifdef DEBUG
    printf("k = %d\n", k);
    printf("边集数组排序前,如下所示.\n"); 
    printf("edges[]     beign       end     weight\n");
    for(i = 0; i < k; i++)
    {
        printf("%d", i);
        printf("        %d", edges[i].begin);
        printf("        %d", edges[i].end);
        printf("        %d", edges[i].weight);
        printf("\n");
    }
#endif
     
    //下面进行排序
    InsertSort(edges, k);
#ifdef DEBUG
    printf("边集数组排序后,如下所示.\n");
    printf("edges[]     beign       end     weight\n");
    for(i = 0; i < k; i++)
    {
        printf("%d", i);
        printf("        %d", edges[i].begin);
        printf("        %d", edges[i].end);
        printf("        %d", edges[i].weight);
        printf("\n");
    }
#endif
}
 
//克鲁斯卡尔算法实现
voidMiniSpanTree_Kruskal(Graph g)  
{
    inti, n, m;
    Edge edges[MAXEDGE];    //定义边集数组
    intparent[MAXVEX];     //定义一数组用来判断边与边是否形成环
     
    //此处为将邻接矩阵转化为边集数组edges并按权值由小到大排序
     
    Convert(g, edges);
    //
     
    for(i = 0; i < g.numVertexes; i++)
    {
        parent[i] = 0;  //初始化数组值为0
    }
 
    for(i = 0; i < g.numEdges; i++)          //循环每一条边
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if(n != m)      //假如n与m不等,说明此边没有与现有生成树形成环路
        {
            parent[n] = m;  //将此边的结尾顶点放入下标为起点的parent中
                            //表示此顶点已经在生成树集合中
            printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
    printf("\n");
}
 
intmain(intargc, char**argv)
{
    Graph g;
     
    //邻接矩阵创建图
    CreateGraph(&g);
     
    //打印网图
    printGraph(g);
     
    //普里姆算法求最小生成树
    MiniSpanTree_Prime(g);
     
    //克鲁斯卡尔算法求最小生成树
    MiniSpanTree_Kruskal(g);   
     
    return0;
}


       以下图为例,进行相应的测试

    

    运行结果如下所示。

    

    

    

    

    

    上述运行过程是这样的:

    (1)输入顶点数、边数;

    (2)输入顶点,和边(依次为起点、终点、权值);

    (3)建立邻接矩阵,用来表示该网图;

    (4)进行普里姆算法进行求最小生成树;

    (5)进行克鲁斯卡尔进行求最小生成树;

            --根据已经建立的邻接矩阵求边集数组;

            --然后进行求最小生成树;    

    

    克鲁斯卡尔算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次,所以克鲁斯卡尔算法的时间复杂度为O(eloge)。《此处不包括由邻接矩阵转为边集数组

    

    对比两个算法,克鲁斯尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。


    

    暂时弄懂了这两个算法,算是重新复习了一下,以后经常看看,不能再忘记了。



    参考:《大话数据结构》、《维基百科


© 著作权归作者所有

小竹zz
粉丝 4
博文 34
码字总数 35733
作品 2
普陀
私信 提问
图算法--最小生成树算法的实现与分析

图是一种灵活的数据结构,它多用于描述对象之间的关系和连接模型。 关于图的算法:最小生成树、最短路径、旅行商问题以及许多其他算法大都会使用到广度优先搜索和深度优先搜索,因为它们提供...

IDreamo
2018/08/21
0
0
加权无向图----Kruskal算法实现最小生成树

上一篇:加权无向图的实现 加权无向图----Prim算法实现最小生成树 数据结构: 用一条优先队列将边按照权重从小到大排序 用union-find数据结构来识别会形成环的边 用一条队列来保存最小生成树...

Superheros
2017/12/20
23
0
【译】Swift算法俱乐部-最小生成树(未加权图)

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
08/02
0
0
数据结构探险之图篇(上)理论篇

数据结构探险之图篇 什么是图? 如下图:无向图 & 有向图 箭头分方向。 无向图中每条认为有来有回两条线 图中的概念: 结点称为顶点。 之间的线称为弧。 弧尾和弧头(箭头)。 从顶点发出去和...

天涯明月笙
2017/09/11
0
0
加权无向图问题--最小代价生成树(Prim算法、kruskal算法)

加权无向图的实现 加权无向图的实现最简单的方法是扩展无向图的表示方法:在邻接表的表示中,可以在链表的结点中增加一个权重域。但这里用另一个方法来实现:我们实现两个类,权重边类和无向...

SuperHeroes
2017/12/20
475
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
319
5
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
11
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部