文章标题-白红宇

文章标题

阅读量：4287 次

发布时间：2019-05-27

本文共 7821 字，大约阅读时间需要 26 分钟。

算法描述：

Kruskal算法是按权值递增的次序来构造最小生成树的方法。

　　　假设G(V,E)最一个具有n个顶点的连通网，顶点集V={v1,v2,….,vn}。设所求的最小生成树为T={U,TE},其中U是T的顶点集，TE是Ｔ的边集，U和TE的初始值为空集。Kruskal算法的基本思想如下：将最小生成树初始化为T=(V,TE),仅包含 G的全部顶点，不包含G的任一条边，此时，T由n 个连通分量组成，每个分量只有一个顶点；将图中G中的边按权值从小到大排序，选择代价最小了一条边，若该边所依附的顶点分属于T中的不同的连通分量，则将此边加入到TE中，否则，舍弃此边而选择下一条代价最小的边。依次类推，直至TE中包含n-1条边（即T中所有的顶点都在同一连通分量上）为止。

算法实现：

　　　设置一个edge数组存储连通网中所有的边，为了便于选择当前权值最小的边，需要将edge中的边按权值从小到大进行排列。

　　　而在连通分量的合并上，可以采用集合的合并方法，对于有n个顶点的连通网，设置一个数组father[0…n-1]，其初始值为-1,表示n个顶点在不同的连通分量上。然后，依次扫描edge数组中的每一条边，并查找相关联的两个顶点所属的连通分量，假设vf1和vf2为两个顶点的所在树的根节点的序号，若vf1不等于vf2，则表明这条边的两个顶点不属于同一个连通分量，则将这条边作为最小生成树的边并输出，然后合并它们所属的两个连通分量。

算法代码：

这里写代码片

int findFather(int father[],int v){    int t = v;    while(father[t] != -1)        t = father[t];    return t;}/* * *Kruskal算法求最小生成树 * */void Kruskal_MG(MGraph MG,Edge edge[]){    int father[MAX_VEX_NUM];    int i,count,vf1,vf2;    // 初始化father数组    for(i = 0;i < MAX_VEX_NUM;i++){        father[i] = -1;    }    i = 0;    count = 0; // 统计加入最小生树中的边数    // 遍历任意两个结点之间的边    while(i < MG.arcnum && count < MG.arcnum){        vf1 = findFather(father,edge[i].start);        vf2 = findFather(father,edge[i].end);        // 如果这两个节点不属于同一个连通分量，则加入同一个连通分量        if (vf1 != vf2){            father[vf2] = vf1;            count++;            printf(%c,%c,%d,MG.vexs[edge[i].start],MG.vexs[edge[i].end],edge[i].cost);        }        i++;    }}

　　　其中，函数findFather的作用就是找指定节点所属的连通分量，在这里也就是找其所在树的根节点在数组中的序号。

算法说明：

　　　对于带权图G中e条边的权值的排序方法可以有多种，这里采用的是最简单的冒泡排序法，时间复杂度为O(n^2)。而判断新选择的边的两个顶点是否在同一个连通分量中，这个问题等价于一个在最多有n 个顶点的生成树中遍历寻找新选择的边的两个节点是否存在的问题，所以此算法的复杂度最坏情况下是O(n^2)。

　　　注意：一般来讲，Prim算法的时间复杂度为O(n^2),因此适合于稠密图，而Kruskal算法需要对e条边进行排序，最快的情况下复杂度为O(elog2e)，因此对于稀疏图，采用Kruskal算法比较合适。

完整代码：

/* * ===================================================================================== * *       Filename:  Kruskal.c * *    Description:  最小生成树之Kruskal算法 * *        Version:  1.0 *        Created:  2015年05月06日 21时25分12秒 *       Revision:  none *       Compiler:  gcc * *         Author:  jesson20121020 (), 997287955@qq.com *   Organization:   * * ===================================================================================== */#include 
   
    #include 
    
     #define MAX_VEX_NUM 50#define MAX_ARC_NUM 100#define UN_REACH 1000typedef char VertexType;typedef enum {    DG, UDG} GraphType;typedef struct {    VertexType vexs[MAX_VEX_NUM];    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];    int vexnum, arcnum;    GraphType type;} MGraph;/** * 根据名称得到指定顶点在顶点集合中的下标 * vex  顶点 * return 如果找到，则返回下标，否则，返回０ */int getIndexOfVexs(char vex, MGraph *MG) {    int i;    for (i = 1; i <= MG->vexnum; i++) {        if (MG->vexs[i] == vex) {            return i;        }    }    return 0;}/** * 创建邻接矩阵 */void create_MG(MGraph *MG) {    int i, j, k,weight;    int v1, v2, type;    char c1, c2;    printf(Please input graph type DG(0) or UDG(1) :);    scanf(%d, &type);    if (type == 0)        MG->type = DG;    else if (type == 1)        MG->type = UDG;    else {        printf(Please input correct graph type DG(0) or UDG(1)!);        return;    }    printf(Please input vexmun : );    scanf(%d, &MG->vexnum);    printf(Please input arcnum : );    scanf(%d, &MG->arcnum);    getchar();    for (i = 1; i <= MG->vexnum; i++) {        printf(Please input %dth vex(char):, i);        scanf(%c, &MG->vexs[i]);        getchar();    }    //初始化邻接矩阵    for (i = 1; i <= MG->vexnum; i++) {        for (j = 1; j <= MG->vexnum; j++) {            if(i == j)                MG->arcs[i][j] = 0;            else                MG->arcs[i][j] = UN_REACH;        }    }    //输入边的信息，建立邻接矩阵    for (k = 1; k <= MG->arcnum; k++) {        printf(Please input %dth arc v1(char) v2(char) weight(int): , k);        scanf(%c %c %d, &c1, &c2,&weight);        v1 = getIndexOfVexs(c1, MG);        v2 = getIndexOfVexs(c2, MG);        if (MG->type == 1)            MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight;        else            MG->arcs[v1][v2] = weight;        getchar();    }}/** * 打印邻接矩阵和顶点信息 */void print_MG(MGraph MG) {    int i, j;    if(MG.type == DG){        printf(Graph type: Direct graph);    }    else{        printf(Graph type: Undirect graph);    }    printf(Graph vertex number: %d,MG.vexnum);    printf(Graph arc number: %d,MG.arcnum);    printf(Vertex set: );    for (i = 1; i <= MG.vexnum; i++)        printf(%c   , MG.vexs[i]);    printf(Adjacency Matrix:);    for (i = 1; i <= MG.vexnum; i++) {        j = 1;        for (; j < MG.vexnum; j++) {            printf(%d   , MG.arcs[i][j]);        }        printf(%d, MG.arcs[i][j]);    }}// 定义边结构体typedef struct{    int start;    int end;    int cost;}Edge;/* * * 由邻接矩阵得到边的信息 * * */void init_edge(MGraph MG,Edge edge[]){    int i,j;    int count = 0;    if(MG.type == 0){        for(i = 1; i <= MG.vexnum;i++){            for (j = 1;j <= MG.vexnum;j++){                if(MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH){                    edge[count].start = i;                    edge[count].end = j;                    edge[count].cost = MG.arcs[i][j];                    count++;                }            }        }    }    else{        for(i = 1; i <= MG.vexnum;i++){            for (j = i;j <= MG.vexnum;j++){                if(MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH){                    edge[count].start = i;                    edge[count].end = j;                    edge[count].cost = MG.arcs[i][j];                    count++;                }            }        }    }}/* * *　将边按权值从大到小排序 * */void sort_edge(Edge edge[],int arcnum){    int i,j;    Edge temp;    for(i = 0; i < arcnum - 1;i++){        for (j = i+1;j < arcnum;j++){            if(edge[i].cost > edge[j].cost){                temp = edge[i];                edge[i] = edge[j];                edge[j] = temp;            }        }    }}/* * * 输出边的信息 * */void print_edge(Edge edge[],int arcnum){    int i = 0;    while(i < arcnum){        printf(%d,%d,%d,edge[i].start,edge[i].end,edge[i].cost);        i++;    }}/***    找出指定节点的所属的连通分量，这里是找出其根节点在father数组中下标。**/ int findFather(int father[],int v){    int t = v;    while(father[t] != -1)        t = father[t];    return t;}/* * *Kruskal算法求最小生成树 * */void Kruskal_MG(MGraph MG,Edge edge[]){    int father[MAX_VEX_NUM];    int i,count,vf1,vf2;    // 初始化father数组    for(i = 0;i < MAX_VEX_NUM;i++){        father[i] = -1;    }    i = 0;    count = 0; // 统计加入最小生树中的边数    // 遍历任意两个结点之间的边    while(i < MG.arcnum && count < MG.arcnum){        vf1 = findFather(father,edge[i].start);        vf2 = findFather(father,edge[i].end);        // 如果这两个节点不属于同一个连通分量，则加入同一个连通分量        if (vf1 != vf2){            father[vf2] = vf1;            count++;            printf(%c,%c,%d,MG.vexs[edge[i].start],MG.vexs[edge[i].end],edge[i].cost);        }        i++;    }}/** * 主函数 */int main(void) {    MGraph MG;    Edge edge[MAX_ARC_NUM];    create_MG(&MG);    print_MG(MG);    init_edge(MG,edge);    sort_edge(edge,MG.arcnum);    printf(the result of Kruskal:);    Kruskal_MG(MG,edge);    return EXIT_SUCCESS;}

运行演示：

jesson@jesson-K43SV:~/develop/worksapce/c_learning/最小生成树$ gcc -o Kruskal Kruskal.cjesson@jesson-K43SV:~/develop/worksapce/c_learning/最小生成树$ ./Kruskal Please input graph type DG(0) or UDG(1) :0Please input vexmun : 4Please input arcnum : 5Please input 1th vex(char):a  Please input 2th vex(char):bPlease input 3th vex(char):cPlease input 4th vex(char):dPlease input 1th arc v1(char) v2(char) weight(int): a b 1Please input 2th arc v1(char) v2(char) weight(int): a c 3Please input 3th arc v1(char) v2(char) weight(int): a d 4Please input 4th arc v1(char) v2(char) weight(int): b c 2Please input 5th arc v1(char) v2(char) weight(int): c d 3Graph type: Direct graphGraph vertex number: 4Graph arc number: 5Vertex set: a  b   c   d   Adjacency Matrix:0   1   3   41000    0   2   10001000    1000    0   31000    1000    1000    0the result of Kruskal:a,b,1b,c,2c,d,3

转载地址：http://kvxgi.baihongyu.com/

你可能感兴趣的文章