数据结构--图--最小生成树

时间:2022-12-09 11:34:33

数据结构–图 –最小生成树

1.基本概念

生成树:一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。

最小生成树:我们把构造连通网的最小代价生成树称为最小生成树。(一棵生成树的代价就是树上各边的代价之和)

2.经典的两种算法

2.1 Prim算法思路

    假设全部顶点的集合是V,已经被挑选出来的是U,那么从集合V-U中不断挑选权值最低的点。(这里的权值最低,是相对于U中所有的点来说,是把U看成一个整体。Prim算法和后面的求最短路径的Dijkstra算法有些相似,具体区别看2.3(Prim算法和Dijkstra算法比较))。
    以某起点为顶点,逐步找各顶点上最小权值的边来构建最小生成树。(这就像是我们如果去参观某个展会,例如世博会,你从一个入口进去,然后找你所在位置周边的场馆中你最感兴趣的场馆观看,看完后再用同样的办法看下一个)

2. 2 Kruskal算法思路

    从宏观着眼,将所有的边排成序列,依次从小到大找边来构建最小生成树。若加入某条边构成回路则舍弃这条边。(这就像是我们参观世博会,事先计划好,进园后直接去到最想看的场馆观看)

2.3

Prim算法与Kruskal算法比较:
Prim算法主要针对顶点展开的,对于稠密图,即边数非常多的情况会更好一些;
Kruskal算法主要针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势。
Prim算法与Dijkstra算法比较[转]1
    在图论中,Prim算法是计算最小生成树的算法,而Dijkstra算法是计算最短路径的算法。二者看起来比较类似,因为假设全部顶点的集合是V,已经被挑选出来的点的集合是U,那么二者都是从集合V-U中不断的挑选权值最低的点加入U,那么二者是否等价呢?也就是说是否Dijkstra也可以计算出最小生成树而Prim也可以计算出从第一个顶点v0到其他点的最短路径呢?答案是否定的,否则就不必有两个算法了。
    二者的不同之处在于“权值最低”的定义不同,Prim的“权值最低”是相对于U中的任意一点而言的,也就是把U中的点看成一个整体,每次寻找V-U中跟U的距离最小(也就是跟U中任意一点的距离最小)的一点加入U;而Dijkstra的“权值最低”是相对于v0而言的,也就是每次寻找V-U中跟v0的距离最小的一点加入U。
    一个可以说明二者不等价的例子是有四个顶点(v0, v1, v2, v3)和四条边且边值定义为(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的图,用Prim算法得到的最小生成树中v0跟v1是不直接相连的,也就是在最小生成树中v0v1的距离是v0->v2->v3->v1的距离是27,而用Dijkstra算法得到的v0v1的距离是20,也就是二者直接连线的长度。

3.算法实现

  • Prim算法

数据结构--图--最小生成树

  • Kruskal算法

数据结构--图--最小生成树

4.代码实现


#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW -2
#define MAX_VERTEX_SIZE 20
#define INFINITY 65535

typedef int Status;
typedef int VertexType;                 //顶点类型
typedef int VRType;                     //顶点关系类型
typedef enum{DG,DN,UDG,UDN} GraphKind;

typedef struct VNode
{
    VertexType data;
}VNode,AdjList[MAX_VERTEX_SIZE];

typedef struct ArcCell
{
    VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];

typedef struct
{
    int vexnum,arcnum;
    AdjMatrix arcs;
    AdjList vertices;
    GraphKind kind;
}MGraph;

typedef struct Edge           // MiniSpanTree_Kruskal算法专用
{
    int begin;
    int end;
    int weight;
}Edge;

Status CreateGraph(MGraph *G){

    VNode v1,v2;
    int i,j,sign1,sign2;
    int value;

    (*G).kind = UDN;

    printf("输入顶点数、弧的数\n");
    scanf("%d%d",&(*G).vexnum, &(*G).arcnum);

    for(i = 0; i < (*G).vexnum; ++i){
        for(j = 0; j < (*G).vexnum; ++j){
            if(i == j)
                (*G).arcs[i][j].adj = 0;
            else
                (*G).arcs[i][j].adj = INFINITY;
        }
    }
    printf("初始化顶点\n");
    for(i = 0; i < (*G).vexnum; ++i){
        scanf("%d",&(*G).vertices[i].data);
    }
    printf("初始化弧\n");
    for(i = 0; i < (*G).arcnum; ++i){
        sign1 = -1;
        sign2 = -1;
        scanf("%d%d%d",&v1.data,&v2.data,&value);
        for(j = 0; j < (*G).vexnum; ++j){
            if(v1.data == (*G).vertices[j].data)
                sign1 = j;
            if(v2.data == (*G).vertices[j].data)
                sign2 = j;
        }
        (*G).arcs[sign1][sign2].adj = value;
        (*G).arcs[sign2][sign1].adj = value;
    }
    return OK;
}

void test(MGraph G){                    //测试函数,打印创建好的邻接矩阵
    int i,j;
    for(i = 0; i < G.vexnum; ++i){
        for(j = 0; j < G.vexnum; ++j)
            printf("%.6d ",G.arcs[i][j]);
        printf("\n");
    }
}

Status MiniSpanTree_Prim(MGraph G){

    int i,j,k,min;
    int adjvex[G.vexnum];
    int lowcost[G.vexnum];

    for(i = 0; i < G.vexnum; ++i){                      //初始化
        lowcost[i] = G.arcs[0][i].adj;
        adjvex[i] = 0;
    }

    lowcost[0] = 0;
    for(i = 1; i < G.vexnum; ++i){                      //找出lowcost[]中的最小值
        min = INFINITY;
        for(j = 1; j < G.vexnum; ++j){
            if(lowcost[j] != 0 && lowcost[j] < min){
                min = lowcost[j];
                k = j;
            }
        }
        lowcost[k] = 0;
        printf("(%d, %d)\n",adjvex[k],k);

        for(j = 1; j < G.vexnum; ++j){                   //更新lowcost[]和adjvex[]
            if(lowcost[j] != 0 && G.arcs[k][j].adj < lowcost[j]){
                lowcost[j] = G.arcs[k][j].adj;
                adjvex[j] = k;
            }
        }

    }
    return OK;
}

Edge* CreateEdges(MGraph G){    //MiniSpanTree_Kruskal算法子函数:对边按权值从小到大的顺序排序


    int i,j;
    int k = 0;
    Edge temp;
    Edge *p;

    p = (Edge *)malloc(G.arcnum * sizeof(Edge));
    if(!p)
        exit(OVERFLOW);

    for(i = 0; i < G.vexnum; ++i){                //初始化
        for(j = i; j < G.vexnum; ++j){
            if(G.arcs[i][j].adj != 0 && G.arcs[i][j].adj != INFINITY){
                p[k].begin = i;
                p[k].end = j;
                p[k].weight = G.arcs[i][j].adj;
                ++k;
            }
        }
    }

    for(i = 0; i < G.arcnum-1; ++i){             //按权值从小到大排序
        for(j = i + 1; j < G.arcnum; ++j){
            if(p[i].weight > p[j].weight){
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
            }
        }
    }
    return p;
}


Status MiniSpanTree_Kruskal(MGraph G){

    Edge *edges;
    int parent[G.vexnum];
    int i,m,n;

    edges = CreateEdges(G);

    for(i = 0; i < G.vexnum; ++i)           //初始化
        parent[i] = 0;

    for(i = 0; i < G.arcnum; ++i){          //循环每一条边
        n = Find(parent,edges[i].begin);
        m = Find(parent, edges[i].end);
        if(n != m){                         //若n与m不等,则说明此边没有与现有生成树形成回路
            parent[n] = m;
            printf("(%d,%d) %d\n",edges[i].begin, edges[i].end, edges[i].weight);
        }

    }
    return OK;
}

int Find(int *parent,int f){            //MiniSpanTree_Kruskal算法子函数 查找连线顶点的尾部下标
    while(parent[f] > 0)
        f = parent[f];

    return f;
}

int main(){

    MGraph G;
    Edge *edges;
    int i;

    CreateGraph(&G);
    printf("创建的邻接矩阵如下:\n");
    test(G);

    printf("MiniSpanTree_Prim:\n");
    MiniSpanTree_Prim(G);

    //MiniSpanTree_Kruskal算法
    printf("将边按权值从小到大排序如下\n");
    edges = CreateEdges(G); 
    for(i = 0; i < G.arcnum; ++i){
        printf("%d %d %d \n",edges[i].begin, edges[i].end, edges[i].weight);
    }
    printf("MiniSpanTree_Kruskal\n");
    MiniSpanTree_Kruskal(G);

    return 0;
}

参考资料:

1.严蔚敏 数据结构 清华大学出版社
2.程杰 大话数据结构 清华大学出版社
3.http://www.cnblogs.com/huiliu/archive/2011/04/15/2017228.html