Kruskal算法

同样是求最小生成树,kruskal适合从边的角度出发,因此适合稀疏图。而prim算法从点的角度出发,适合稠密图。

时间复杂度为O(eloge)。因为外层循环了e(边数)层,而内部find循环了loge层。

算法首先把二维矩阵图转化为边图

    for(i=0;i<MAXSIZE;i++){
        for(j=0;j<MAXSIZE;j++){
            flag = 1;
            if(i != j && num[i][j] != INF){
                    for(k=0;k<=max;k++){
                        if(g->e[k].begin == j && g->e[k].end == i){
                            flag = 0;
                            break;
                        }
                    }
                    if( flag ){
                        g->e[max].begin = i;
                        g->e[max].end = j;
                        g->e[max].length = num[i][j];
                        //printf("[%d]%d %d %d \n",max,g->e[max].begin,g->e[max].end,g->e[max].length);
                        max++;
                    }
            }
        }    
    }

通过冒泡排序,排序边数组

void bubblesort(Graph *g,int len){
    int i,j;
    for(i=0;        i < len;    i++){
        for(j = len-1;    j>i;    j--){
            if(g->e[j].length < g->e[i].length){
                swap(g,i,j);
            }
        }
    }
}

void swap(Graph *g,int i,int j){
    edge *pool = (edge *)malloc(sizeof(edge));
    
    pool->begin = g->e[j].begin;
    pool->end = g->e[j].end;
    pool->length = g->e[j].length;

    g->e[j].begin = g->e[i].begin;
    g->e[j].end = g->e[i].end;
    g->e[j].length = g->e[i].length;

    g->e[i].begin = pool->begin;
    g->e[i].end = pool->end;
    g->e[i].length = pool->length;

    free(pool);
}

最后通过kruskal,从最小便开始,连接图。

for(i=0;i<max;i++){
        n = find(parent,g->e[i].begin);
        m = find(parent,g->e[i].end);

        if(n != m){
            parent[n] = m;
            printf("[%d %d] %d \n",g->e[i].begin,g->e[i].end,g->e[i].length);
        }
    }

全部代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 9
#define INF 65535

typedef struct edge{
    int begin;
    int end;
    int length;
}edge;
typedef struct Graph{
    edge e[20];
}Graph;
int num[MAXSIZE][MAXSIZE]={ 
                 0,  10, INF,INF,INF,11, INF,INF,INF,
                 10,      0,  18, INF,INF,INF,16, INF,12,
                 INF,INF,0,  22, INF,INF,INF,INF,8,
                 INF,INF,22, 0,  20, INF,INF,16, 21,
                 INF,INF,INF,20, 0,  26, INF,7,  INF,
                 11, INF,INF,INF,26, 0,  17, INF,INF,
                 INF,16, INF,INF,INF,17, 0,  19, INF,
                 INF,INF,INF,16, 7,  INF,19, 0,  INF,
                 INF,12, 8,  21, INF,INF,INF,INF,0};


void bubblesort(Graph *g,int len); 
void swap(Graph *g,int i,int j);
int find(int *p,int n);
int main(){
    int parent[20] = {0};
    int i,j,k,n,m;
    int max=0;
    int flag = 1;
    
    Graph *g = (Graph *)malloc(sizeof(Graph));

    for(i=0;i<MAXSIZE;i++){
        for(j=0;j<MAXSIZE;j++){
            flag = 1;
            if(i != j && num[i][j] != INF){
                    for(k=0;k<=max;k++){
                        if(g->e[k].begin == j && g->e[k].end == i){
                            flag = 0;
                            break;
                        }
                    }
                    if( flag ){
                        g->e[max].begin = i;
                        g->e[max].end = j;
                        g->e[max].length = num[i][j];
                        //printf("[%d]%d %d %d \n",max,g->e[max].begin,g->e[max].end,g->e[max].length);
                        max++;
                    }
            }
        }    
    }
    printf("\n");

    bubblesort(g,max);

    for(i=0;i<max;i++){
        printf("%d %d %d \n",g->e[i].begin,g->e[i].end,g->e[i].length);
    }
    
    

    for(i=0;i<max;i++){
        n = find(parent,g->e[i].begin);
        m = find(parent,g->e[i].end);

        if(n != m){
            parent[n] = m;
            printf("[%d %d] %d \n",g->e[i].begin,g->e[i].end,g->e[i].length);
        }
    }
    getchar();
    return 0;
}
int find(int * p,int n){
    while(p[n] > 0)
        n = p[n];
    return n;
}
void bubblesort(Graph *g,int len){
    int i,j;
    for(i=0;        i < len;    i++){
        for(j = len-1;    j>i;    j--){
            if(g->e[j].length < g->e[i].length){
                swap(g,i,j);
            }
        }
    }
}

void swap(Graph *g,int i,int j){
    edge *pool = (edge *)malloc(sizeof(edge));
    
    pool->begin = g->e[j].begin;
    pool->end = g->e[j].end;
    pool->length = g->e[j].length;

    g->e[j].begin = g->e[i].begin;
    g->e[j].end = g->e[i].end;
    g->e[j].length = g->e[i].length;

    g->e[i].begin = pool->begin;
    g->e[i].end = pool->end;
    g->e[i].length = pool->length;

    free(pool);
}

运行结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

423. 有效的括号序列利用堆栈

给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。

13360
来自专栏令仔很忙

新手学JAVA(七)----Override VS Overload

在同一个类中的许多方法可以拥有相同的名字,只要他们的参数声明不同即可,这种方法被称为重载。 举个例子:

10320
来自专栏Java架构沉思录

深入浅出排序算法(上)

前言 排序指的是按照某种顺序(升序或降序)排列序列元素的一种算法,在实际工作中用得非常多,也是面试中经常被问到的知识点。本文将为大家介绍常见的几种排序算法的思...

28650
来自专栏老马说编程

(20) 为什么要有抽象类? / 计算机程序的思维逻辑

基本概念 上节提到了一个概念,抽象类,抽象类是什么呢?顾名思义,抽象类就是抽象的类,抽象是相对于具体而言的,一般而言,具体类有直接对应的对象,而抽象类没有,它...

26370
来自专栏程序员互动联盟

【编程基础】Java初始化有何玄机?

对于Java的初始化顺序大家应该清楚,之前在网站上面有专门的讲解,大家可以通过文章下面的“查看原文”来阅读。 初始化顺序总结起来就是: 1、无继承情况的初始化顺...

37790
来自专栏积累沉淀

JavaScript对象和数组

学习要点: 1.Object类型 2.Array类型 3.对象中的方法 什么是对象,其实就是一种类型,即引用类型。而对象的值就是引用类型的实例。 一...

32650
来自专栏猿人谷

static_cast ,reinterpret_cast

用法:static_cast < type-id > ( expression ) 该运算符把expression转换为type-id类型,但没有运行时类型检查...

272100
来自专栏DHUtoBUAA

查找数组中重复的数字

        题目来源于《剑指Offer》中的面试题3:找出数组中重复的数字。   // 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中...

47960
来自专栏GreenLeaves

JavaScript引用类型之Array数组的toString()和valueof()方法的区别

一、转换方法 1、在JavaScript中几乎所有对象都具有toLocaleString()、toString和valueof()方法,因为,所有的对象都继承自...

22970
来自专栏程序员互动联盟

【专业技术第二讲】c语言中const的使用

遇到有人为const的使用: ? 这里对const的使用做一个大致的总结。 C语言的const关键字与指针搭配使用,const是C语言中保留的一个关键字,它用来...

36460

扫码关注云+社区

领取腾讯云代金券