算法提升:图的最小生成树算法-克鲁斯卡尔(Kruskal)

这篇具有很好参考价值的文章主要介绍了算法提升:图的最小生成树算法-克鲁斯卡尔(Kruskal)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

概念

思路

代码


概念

克鲁斯算法最小生成树,算法,图论,算法,数据结构

克鲁斯卡尔算法查找最小生成树的方法是:将连通网中所有的边按照权值大小做升序排序,从权值最小的边开始选择,只要此边不和已选择的边一起构成环路,就可以选择它组成最小生成树。对于 N 个顶点的连通网,挑选出 N-1 条符合条件的边,这些边组成的生成树就是最小生成树。

举个例子,图 1 是一个连通网,克鲁斯卡尔算法查找图 1 对应的最小生成树,需要经历以下几个步骤:
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 1 连通网


1) 将连通网中的所有边按照权值大小做升序排序:
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


2) 从 B-D 边开始挑选,由于尚未选择任何边组成最小生成树,且 B-D 自身不会构成环路,所以 B-D 边可以组成最小生成树。
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 2 B-D 边组成最小生成树


3) D-T 边不会和已选 B-D 边构成环路,可以组成最小生成树:
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 3 D-T 边组成最小生成树


4) A-C 边不会和已选 B-D、D-T 边构成环路,可以组成最小生成树:
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 4 A-C 边组成最小生成树


5) C-D 边不会和已选 A-C、B-D、D-T 边构成环路,可以组成最小生成树:
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 5 C-D 边组成最小生成树


6) C-B 边会和已选 C-D、B-D 边构成环路,因此不能组成最小生成树:
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 6 C-B 边不能组成最小生成树


7) B-T 、A-B、S-A 三条边都会和已选 A-C、C-D、B-D、D-T 构成环路,都不能组成最小生成树。而 S-A 不会和已选边构成环路,可以组成最小生成树。
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 7 S-A 边组成最小生成树


8) 如图 7 所示,对于一个包含 6 个顶点的连通网,我们已经选择了 5 条边,这些边组成的生成树就是最小生成树。
 

克鲁斯算法最小生成树,算法,图论,算法,数据结构


图 8 最小生成树

思路

整个K算法中,其实简单的说就包含两个步骤:

  1. 找出路径中最短的边;
  2. 看这个边会不会对现有的边形成环路,如果会就丢弃,如果不会就记录;

难点就是判断会不会有环,这里可以使用到并查集的思想去做,也可以直接使用一个集合,把所有的节点放入集合,如果下一次选中的边两个节点都在集合中可以被找到,那就说明会导致环路。文章来源地址https://www.toymoban.com/news/detail-773825.html

代码

#include <stdio.h>
#include <stdlib.h>
#define N 9   // 图中边的数量
#define P 6   // 图中顶点的数量
//构建表示边的结构体
struct edge {
    //一条边有 2 个顶点
    int initial;
    int end;
    //边的权值
    int weight;
};

//qsort排序函数中使用,使edges结构体中的边按照权值大小升序排序
int cmp(const void* a, const void* b) {
    return  ((struct edge*)a)->weight - ((struct edge*)b)->weight;
}
//克鲁斯卡尔算法寻找最小生成树,edges 存储用户输入的图的各个边,minTree 用于记录组成最小生成树的各个边
void kruskal_MinTree(struct edge edges[], struct edge minTree[]) {
    int i, initial, end, elem, k;
    //每个顶点配置一个标记值
    int assists[P];
    int num = 0;
    //初始状态下,每个顶点的标记都不相同
    for (i = 0; i < P; i++) {
        assists[i] = i;
    }
    //根据权值,对所有边进行升序排序
    qsort(edges, N, sizeof(edges[0]), cmp);
    //遍历所有的边
    for (i = 0; i < N; i++) {
        //找到当前边的两个顶点在 assists 数组中的位置下标
        initial = edges[i].initial - 1;
        end = edges[i].end - 1;
        //如果顶点位置存在且顶点的标记不同,说明不在一个集合中,不会产生回路
        if (assists[initial] != assists[end]) {
            //记录该边,作为最小生成树的组成部分
            minTree[num] = edges[i];
            //计数+1
            num++;
            elem = assists[end];
            //将新加入生成树的顶点标记全部改为一样的
            for (k = 0; k < P; k++) {
                if (assists[k] == elem) {
                    assists[k] = assists[initial];
                }
            }
            //如果选择的边的数量和顶点数相差1,证明最小生成树已经形成,退出循环
            if (num == P - 1) {
                break;
            }
        }
    }
}

void display(struct edge minTree[]) {
    int cost = 0, i;
    printf("最小生成树为:\n");
    for (i = 0; i < P - 1; i++) {
        printf("%d-%d  权值:%d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
        cost += minTree[i].weight;
    }
    printf("总权值为:%d", cost);
}

int main() {
    int i;
    struct edge edges[N], minTree[P - 1];
    for (i = 0; i < N; i++) {
        scanf("%d %d %d", &edges[i].initial, &edges[i].end, &edges[i].weight);
    }
    kruskal_MinTree(edges, minTree);
    display(minTree);
    return 0;
}

到了这里,关于算法提升:图的最小生成树算法-克鲁斯卡尔(Kruskal)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 大话数据结构-普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)

       构造连通网的最小代价生成树称为最小生成树,即Minimum Cost Spanning Tree ,最小生成树通常是基于无向网/有向网构造的。   找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。   普里姆算法,即Prim算法,大致实现过程如下:   (1) 新建数组

    2024年02月05日
    浏览(46)
  • 图的最小生成树算法

    任务描述 本关任务:图的存储结构为邻接矩阵,要求编写函数利用普里姆(Prim)算法求图的最小生成树。 测试说明 平台会对你编写的代码进行测试: 测试输入: 3 lt3.txt 0 输入说明: 第一行输入3,表示输入图的类型为无向网。 第二行输入文件名,该文件里保存了图的数据

    2024年02月06日
    浏览(34)
  • 图的最小生成树-Prim算法

    目录 问题引入  程序设计  程序分析 本节文章 【问题描述】 编写程序,利用带权无向图的邻接矩阵存储,实现图的最小生成树Prim算法。 【输入形式】 输入图的顶点序列及图的边的情况。如样例所示。边的输入以输入-1,-1,-1,作为结束。 0,1,6 表示对应的顶点及边是:

    2024年02月08日
    浏览(53)
  • 图的最小生成树-Kruskal算法

    目录 问题引入  程序设计  程序分析 本节文章 【问题描述】 编写程序,利用带权无向图的邻接矩阵存储,实现图的最小生成树Kruskal算法。

    2024年02月08日
    浏览(58)
  • 求无向连通图的最小生成树 ← Prim算法

    【题目描述】 给定一个 n 个点 m 条边的 无向连通图 。图中可能存在 重边 和 自环 ,边权可能为 负数 。 利用Prim算法求此种无向连通图的最小生成树的树边权重之和。 【输入格式】 第一行包含两个整数 n 和 m。 接下来 m 行,每行包含三个整数 u,v,w,表示点 u 和点 v 之

    2024年02月07日
    浏览(53)
  • 图的最小生成树算法(图解+代码)| 学不会来看我系列

    在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-

    2023年04月12日
    浏览(76)
  • 【数据结构与算法】图的搜索——广度优先遍历、最小生成树

    邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍. 邻接矩阵:用于最短路径算法. 该数据结构维护一个不相交动态集的集合,每个集合有一个代表,不关心谁做代表。 支持三种操作: MAKE_SET(x) FIND_SET(x) UNION(x,y

    2024年02月19日
    浏览(50)
  • 【数据结构】无向图的最小生成树(Prime,Kruskal算法)

    连通图 :在 无向图 中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中 任意一对顶点都是连通的 ,则称此图为连通图 强连通图 :在 有向图 中,若在每一对顶点vi和vj之间都存在一条从vi到vj的路径,也存在一条从vj到vi的路径,则称此图是强连通图 生成

    2024年01月24日
    浏览(48)
  • 求无向图的最小生成树——Kruskal算法(超详细)【并查集,python实现】

    以如下无向图为例,求最小生成树及其权值。 补充知识点: 最小生成树(不官方的解释):包含所有节点,保持整个图连通,所有边权值之和最小。 1、补充在前 (1)图的存储 采用二维列表存储(点,点,边的权值) (2)顶点转换 为了便于计算,将字母A ~ G用数字0 ~ 6代

    2024年02月04日
    浏览(45)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包