精华内容
下载资源
问答
  • 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 构造网的最小生成树必须解决下面两个问题: 1、尽可能选取权值小的边,但不...
  • 假设 WN=(V,{E}) 是个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是个含有 n 棵树的...
  • 请输出无向连通图最小生成树权重之和。 输入 第行是2个整数,分别表示顶点n和边m。接下来的m行中,每行第个整数表示边的开始顶点,第二个表示边的结束顶点,第三个表示这条边的权重。 ( 测试数据中保证图...
  • 最小生成树 生成树与生成森林 最小生成树 小结与作业 生成树 一定义 图G生成树是G极小连通子图即包含G中所有顶点n与n-1条边连通子图 生成树 V1 V2 V3 V4 V5 V8 V6 V7 V1 V2 V4 V8 V5 V3 V6 V7 V1 V2 V3 V4 V5 V8 V6 ...
  • 最小生成树(最小代价树) 对于⼀个带权连通⽆向图G = (V, E),⽣成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有⽣成树的集合,若T为R中边的权值之和最⼩的⽣成树,则T称为G的最...

    一、最小生成树

    • 连通图生成树包含图中全部顶点的一个极小连通子图。
    • 边尽可能的少,但要保持连通
    • 若图中顶点数为n,则它的生成树含有 n-1 条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。
      在这里插入图片描述

    (一)最小生成树(最小代价树)

    • 对于⼀个带权连通⽆向图G = (V, E),⽣成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有⽣成树的集合,若T为R中边的权值之和最⼩的⽣成树,则T称为G的最⼩⽣成树(Minimum-Spanning-Tree,MST)
      在这里插入图片描述
    • 最小生成树可能有多个,但边的权值之和总是唯一且最小的
    • 最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通,增加一条边则会出现回路
      在这里插入图片描述

    (二)Prim 算法(普里姆)

    • Prim 算法(普里姆):从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。
    • P城开始进行建成生成树。
      在这里插入图片描述
    • 农场开始进行建成生成树。 在这里插入图片描述
    • 通过不同的结点开始,建成的最小生成树结构有可能不一样。
      在这里插入图片描述

    (三)Kruskal 算法(克鲁斯卡尔)

    • Kruskal 算法(克鲁斯卡尔):每次选择⼀条权值最⼩的边,使这条边的两头连通(原本已经连通的就不选)直到所有结点都连通。
      在这里插入图片描述

    (四)Prim 算法 v.s. Kruskal 算法

    在这里插入图片描述

    1. Prim 算法的实现思想

    • 初始:从V0开始
      在这里插入图片描述
    • 第1轮:循环遍历所有个结点,找到lowCost最低的,且还没加⼊树的顶点
      在这里插入图片描述
      在这里插入图片描述
    • 第2轮:循环遍历所有个结点,找到lowCost最低的,且还没加⼊树的顶点
      在这里插入图片描述
      在这里插入图片描述
    • 第3轮:循环遍历所有个结点,找到lowCost最低的,且还没加⼊树的顶点
      在这里插入图片描述
      在这里插入图片描述
    • 第4轮:循环遍历所有个结点,找到lowCost最低的,且还没加⼊树的顶点
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 第5轮:循环遍历所有个结点,找到lowCost最低的,且还没加⼊树的顶点
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    2. Kruskal 算法的实现思想

    • 初始:将各条边按权值排序
      在这里插入图片描述
    • 第1轮:检查第1条边的两个顶点是否连通(是否属于同⼀个集合)
      在这里插入图片描述
    • 第2轮:检查第2条边的两个顶点是否连通(是否属于同⼀个集合)
      在这里插入图片描述
    • 第3轮:检查第3条边的两个顶点是否连通(是否属于同⼀个集合)
      在这里插入图片描述
    • 第4轮:检查第4条边的两个顶点是否连通(是否属于同⼀个集合)
      在这里插入图片描述
    • 第5轮:检查第5条边的两个顶点是否连通(是否属于同⼀个集合)
      在这里插入图片描述
    • 第6轮:检查第6条边的两个顶点是否连通(是否属于同⼀个集合)
      在这里插入图片描述
    • 共执⾏ e 轮,每轮判断两个顶点是否属于同⼀集合,需要 O(log2e)总时间复杂度 O(elog2e)
    展开全文
  • 最小生成树算法

    2021-03-06 13:56:38
    [音乐] [音乐] [音乐] [音乐] 各位大家好,本次介绍最小生成树相关知识点 个小镇它一共有五座房子,有天他们商量好 在房屋下面修建逃生通道使之互相相连 但是同时他们又希望开发代价比较小,在通过 和开发商协商...

    [音乐] [音乐] [音乐] [音乐] 各位大家好,本次介绍最小生成树相关知识点 一个小镇它一共有五座房子,有一天他们商量好 在房屋下面修建逃生通道使之互相相连 但是同时他们又希望开发代价比较小,在通过 和开发商协商之后,他们得到了如图所示的 这样一个开发代价信息图,那么请问最节省成本的开发方案是什么? 我们把这个问题形式化一下 首先需要引入两个定义,第一个是带权图 带权,我们称G是一个带权图,它包含三个信息 顶点信息、 边信息,以及一个新的权重信息 w是一个函数,它将对每一条边赋予一个权值 而最小生成树的问题是说,给了这样一个带权图之后 我们要找它所有生成树中代价最小的那棵树 有的时候我们对w(G)这样一个符号,我们使用w(G)这样一个符号来表示 G中所有边的权重之和 我们想强调一点就是,最小生成树不一定唯一 在图中的这样一个,注意我们这里用带圈的数字来表示顶点的名字,而把 权重直接标志在边上 我们说这个图它有两个不同的最小生成树,使用 ①②和②③边,或者是使用①③和②③边,它们的权重是一样,并且都是原图的 生成树。 我们 自然而然地会回忆Caley定理,Caley定理是说n个顶点能够形成的不同的树 一共有n的n-2次方种,当n=5的时候 n的n-2次方,表现为125种不同的生成树 在这个规模,计算机当然可以轻松地处理,我们找到原始问题中的 最小的这样开掘代价为红线所表示的这样一个开掘方案 但是如果这个城镇扩张了,它变成了十座房子,我们可以看到现在 根据Caley定理,就有10的8次方,有一亿种可能的开掘方案 那么当n=20的时候,我们的开掘方案的数量 猛增到了10的20次方,这就是一个天文数字,计算机无法处理 更不要说n继续增加的时候,但是我们想说 寻找最小生成树这个问题,其实有非常快速的算法 这也是我们本次课想要介绍的第一个算法,是Kruskal算法 Kruskal算法我们先通过一个实例来介绍它的运行,然后我们 会形式化地定义什么是Kruskal算法,并最后给出Kruskal算法正确性的证明 在给出的这张图中,一共有七个顶点 我们也在相应的边上,标上了权重 Kruskal算法它说我先把所有边的权重,按照一个永远不会递减的这样一个 顺序排好,我接下来的工作呢就是要把 这些边加回到这些顶点集合中,使得 右边的这些点,生成原来图的一棵树,一个生成树 首先我们使用的是原始图中权重最小的边 是1这个边,我们把它加入目标的生成树 我们接下来寻找在没有考虑过的边中 权重最小的是2,我们把2加入 目标生成树,下一个没有考虑并且最小的边的权重是3,我们把3加入 但是这个时候问题出现了,我们说新加入的这条边和原来的边形成了一个环,这个时候 我们把3这条边去掉,不使用。 我们继续寻找下一条没有使用过,并且权重最小的那个边 这里是4,我们把4加回来。 注意在这里的时候,原始的七个 独立的点,现在变成了四个连通分支 加了4之后,我们继续寻找下一个权重最小并且没使用过的是5,5加进来 我们接着,5之后是6,6又形成了环,我们不使用 我们使用7,7不形成环 再使用10,10又出现环,同样地,不再使用 我们继续寻找,一直找到了14这条边 注意到这个时候右边的图已经形成了原始的 图的一个生成树,我们说这个时候我们的算法终止 并且我们声称我们所找到的这棵树就是一棵最小生成树 好了,我们这里介绍一下Kruskal算法的形式化描述 Kruskal算法的输入是一个连通的带权图,而输出是这个连通带权图的最小生成树 我们这个算法怎么做呢?它第一步是先把E中的边 按照从小到大的顺序排好,或者叫做一个不递减的序这样一个排好 第二步我们初始化两个集合,一个是T集合,一个是E'集合,T集合其实是目标的 生成树集合,而E'是还未使用过的边集 我们说如果当T的规模小于n-1的时候,我们就继续在还没有考虑过的边集中 寻找权重最小的那个边,我们把这个边加入到T中 我们考察这样的一个图是否会含有环 如果没有环,那么我们说这个边的加入是 合适的,或者换句话说我们就在T中加入这条边,并且 将这条边从E'中移出 如果有环,那么我们就,T就不更新 这条边不能使用。 这个时候我们同样地需要更新E' 使得未使用过的边的集合减少1 所以大家可以看到,无论有环或者没环,E'的大小严格地减少 所以这个算法一定会终止,当这个算法终止的时候 我们输出最后的那个T,就是我们所要寻找的最小生成树 当然我们给出了算法,我们总是要说明它的正确性 这个正确性其实包含两个方面,第一个要说明这个算法它确实 确实会在n-1的时候 这个规模的时候停止,这个是比较容易说明的,因为大家可以看到 一开始我们的集合是所有的 n个顶点,而我们每一步,算法的每一步所做的事情 其实是每一次减少一个连通分支,那么 我们知道原始又是一个连通图,那么经过n-1步之后,它必然会 终止。 刚才我们提了 Kruskal算法一定会在T的规模正好等于n-1的时候停下来 接下来我们想要说,它生成的不仅是一棵树,并且是一棵最优的树 那么怎么样说明它是最优的树呢?那我们只需要说明Kruskal算法输出的这棵树 它的权重比任何一棵原图G的 生成树的权重都要小,那么就说明 我们这里用T来表示Kruskal算法的输出,并且 任取一棵生成树叫T0* 既然T和T0*可能不一样,那么我们用e来表示 依照Kruskal算法的顺序被加入T 中的第一条不在,不出现在Ti*中的边 注意,我这里用的是i,是为了后面好说明,一开始i就是0 e的两个边,顶点我们称为u和v 现在我们做了一件什么事?我们把e这个边加回到T0*中 但是又由于我们已经知道T0*是原始图的一棵生成树 所以我们知道u和v之间本来已经有一个边了 u和v之间已经有一条路径 那么又由于树是最大的 无环图,那么e的加入必定导致图中出现一个环 这里我们想说,从u到v的这个路径上,必然 用到了一条边,这条边呢它不出现在T中 这个很容易说明,因为如果u到v的所有 边都已经出现在T中的话,那么T本身就是含环,这也与我们的算法相违背 并且我们要说,这个e'它不仅仅是只出现在T0*中,并且它的权重 至少和e一样大,为什么?因为如果它的权重严格地小于e,那么 根据Kruskal算法的 设计,我们总是先使用权重比较小的边,那么e'之前就应该被用到 这个时候我们更新T0*,我们把它得到 Ti*,Ti*是从T0*中删掉e'这个边 而把e这个边加入,大家可以看到 因为我们加入了一条权重不会高于原来权重被删 掉的边的权重的边,所以新得到的这棵树它的权重不会比原来树的权重要 高。 这里我们得到一个最重要的观察。 我们说 T 和 T1* 相比,它 与 T0* 之间的差距又减少了 1 或者换一句话说 e 这条边共享于 T1* 和 T 之间 而且与此同时我们刚才这个 论证过程可以,可以一直往返 我们的每次得到新的这样一个,带 * 的这样一棵树,它的权重总不会比原来树的权重要 大,或者换句话说它总是小于等于原来树的那个权重,最后我们这个 T 最终会到达一棵树,它和这棵树之间是 完全是一样的,并且这棵树的权重一定是小于等于原始的 T0* 换句话说我们就证明了 T 这棵树的权重一定是小于等于任何一棵 原始图中生成树的权重,也就是说 T 是最优生成树 好了,我们回顾一下 Kruskal 算法。 Kruskal 算法的 核心是对边进行一个权重的排序。 然后我们每次都试图去使用那个 没使用过的权重最小的边。 那么我们想要介绍第二种算法叫 Prim 算法, Prim 算法 非常不一样,它是从点出发来考虑问题。 还是同样一个例子 但我们现在把点分成两个集合,第一个集合叫 X 集合,第二个集合叫做 Y 集合 开始的时候 X 集合只含有一个点,随便一个点,我们这里取 1,用黄色表示 而 Y 集合中的点就是除了 1 之外的顶点 这个时候我们要标记所有跨越在 X 集和 Y 集之间的边。 大家可以看到我用虚线表示了 跨越了 X 和 Y 之间的那个可能的边,它包含了 R 这条边 以及权重为 1 的这条边。 Prim 算法说我这个时候我取权重最小的那个边 我这里取 1 ,并且把这个边的另外一个顶点 2 也加入 X 集合 虚线中间所勾画出这个所包括就是 X 集合,余下的都是 Y 集 那么我们同样看 X 和 Y 这两个集合之间,跨这两个集合的边,权重最小的是哪一个呢? 在这里是 2,我们就进一步扩展 X,把 4 放进去 现在 X 包含了 3 个点,类似的 我们找到跨两个集合的边中,权值最小的是 5 把 7 放进去,继续寻找,找到最小的是 4 把 4 放进去,进一步扩大找到最小的 是 7,把 7 放进去。 我们到最后一步,我们为了把 5 放进去,我们观察 X 和 Y 跨越 X 和 Y 的那个边,权重最小是 14 这就是我们最后 Prim 算法的输出 可以看到它和 Kruskal 算法输出了同样一棵最小生成树 Prim 算法的形式化描述是这样,同样它的输入是一棵带权图 而它的输出是最小生成树。 算法描述式我们维持 三个集合。 第一个是 T 集合,是目标生成树集合。 第二个是 X 集合 初始化包含任何一个点。 我们一开始,所以不是一般性,我们假设它就 包含了标号为 1 的这个点。 Y 是说除了 X 中间 的点,我们把它都记为 Y 中的点 当 Y 还不为空的时候,那么我们怎么样做呢?我们去找 X 和 Y 这两个集合,跨越这两个集合的边中权值最小的边 我们把这个边记为 e,它的两个顶点分别记为 x 和 y。 我们假设 x 已经在 X 中,y 已经在 Y 中。 那么我们可以更新 X 是怎么样更新?我们将把这个 Y 中的这个点 y 放到 X 中,而与此同时 Y 中的点会减少一个 而 T 的更新是怎样的呢?我们就会把这个 所找到的这个跨越两个集合全是最小的边放到 T 中来 最后我们会输出 T,注意输出 T 的时候,就是说 Y 是空集,Y 是空集,所有的点都被使用到 可以看到 Prim 算法和 Kruskal 算法的思想还是非常不一样。 这里的重点的考察对象 是点。 我们想说 Prim 算法的正确性。 首先它显然会输出一个连通图,因为每一步 我们都是把一个点加入到 X 中,而 X 中本身可以 归纳的这么一个,一定是一个连通图 同时又由于我们每次所用的边都是跨了 X 和 Y 两个集合,所以我们一定不会引入环 好了,我们刚才分析了 Prim 算法,我们说算法每一步 都是在不断地生长一棵树,所以它的输出一定是一棵树 那么为了证明正确性呢,我们只需要证明它确实是权重 最小的这样一棵树。 类似于 Kruskal 算法的证明,我们假设 Prim 算法的输出 是 T,我们假设任何任取一棵原图集的生成树,我们用 T0* 来表示 我们假设如果 T 和 T0* 不一样 那么我们用 e 来表示,依照算法被加入 T 的第一条 不在 T0* 中的边,这里我仍然是用 Ti*,i 后来会被 不断地更新。 这个 e 的两个端点分别是 u 和 v 我们现在同样地把 e 这个边加入 T0* 中。 我们说因为原始的 T0* 是一棵树,所以说把 e 加入之后,它必然产生一个环 但是我们考虑在加入 e 之前 的 X 集合,X 集合因为它所对应的、 它所对应的 这样一个连通分支,它跟 Y 之间到底是什么关系呢? 因为我们刚刚提到了,加入 e 之后会有一个环,所以我们知道在 X 和 Y 之间 对 T0* 而言必然存在另外一条边是 e' 那么我们说,我们在 运行 Prim 算法的时候选择的加入 e,而没有选择 e' 的可能性只有一个,那么就是 e' 的权重 大于等于 e 这个边的权重 同样,类似 Kruskal 的算法的证明,我们这个时候更新 T0* 为 T1* T1* 说我们把 T0* 中原始的边 e' 删掉。 我们删掉一个权重 偏大一些的边,偏大或者相等的边,而加入一条新的边叫做 e 那么显然 T1* 的权重 不会高于 T0* 的权重,并且 T1* 一定也是一棵树。 因为我们 是从一个环中删掉了一个边,并且它仍然是 保持了原图的连通性。 这里我们同样 从 T0* 到 T1* 我们实现了一件什么事?从 T0* 到 T1* 它们跟 T 的相似度增加了 1,但是 T1* 的权重小于等于原始 T0* 的权重 我们可以继续这样的一个论证过程。 从 T0* 得到 T1* 得到 T2* 等等,直到 T 和某一个 T 阶星它们完全相等 但是又由于我们保持了权重这样一个不会增加的这样一个关系,所以我们得到 最后的 WT 阶星,它的权重一定是小于等于原始的 WT0* 换句话说,T 的权重一定是小于等于任何一棵原图的 生成树,也就证明了我们根据 Prim 算法 所得到的这个树 T 确实是一棵最优的生成树 这里我们就介绍好了有关最小生成树的定义,以及它的两个基本算法 谢谢大家!

    展开全文
  • 1、 对无向图求每个顶点的度,或对有向图求每个顶点的入度和出度(2、 完成插入顶点和边(或弧)的功能3、 完成删除顶点和边(或弧)的功能 ...15、求最小生成树 16、对于有个源点和个汇点的有向网,求关键路径
  • 最小生成树

    2021-01-31 19:48:48
    最小生成树 最小生成树概念 定义给定一张边带权的无向联通图G = (V,E), n = |V|,m=|E|。由V中全部 顶点和E中n-1条边构成的无向联通子图被称为G的棵生成树。边的权值之和最小的的生成树被称为无向图G的最小生成树...

    最小生成树

    最小生成树概念

    定义给定一张边带权的无向联通图G = (V,E), n = |V|,m=|E|。由V中全部
    顶点和E中n-1条边构成的无向联通子图被称为G的一棵生成树。边的权值之和最小的的生成树被称为无向图G的最小生成树(Minimum Spanning Tree,MST)

    1>是一棵树: 无回路,n个顶点一定有n-1条边
    2>是生成树: 包含全部顶点,n-1条边都在图中
    3>边的权重和最小

    主要思想 贪心,每一步要求最小

    kruskal算法

    其基本思想是:假设连通网G=(V,E),令最小生成树的初始状态为只有N个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点分别在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止。
    通俗点讲:KRUSKAL算法在找最小生成树结点之前,需要对边权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中(如果加入时产生回路就跳过这条边,加入下一条边),当加入的边数为N - 1条后,就找到了这个连通图的最小生成树。

    核心代码 运用到了并查集的思想

    const int inf = 0x3f3f3f3f;
    const int MAXN = 110;
    int vis[1111];
    
    struct QAQ {
        int l, r, val;//依次分别表示左边这个点,右边这个点,两点的边的权值
        bool operator<(const QAQ &tt) const {
        //重载运算符,用于结构体比较
            return val < tt.val;
        }
    } dis[MAXN * MAXN];
    
    int find(int x) {//并查集
        return x == vis[x] ? x : vis[x] = find(vis[x]);
    }
    
    void kruskal(int m, int n) {
        int sum = 0;
        int num = 0;
        for (int i = 1; i <= m; i++)vis[i] = i;//每个点各自为一个集合
        for (int i = 1; i <= n; i++) {//遍历n对点
            int f1 = find(dis[i].l);//左边点对应的集合
            int f2 = find(dis[i].r);//右边点对应的集合
            if (f1 != f2) {//不在一个集合说明没有加入到生成树
                sum += dis[i].val;//最小生成树的边权和
                vis[f1] = f2;//并入最小生成树的集合
            }
        }
    }
    
    

    prime算法(个人感觉就像是最短路的Dijkstra算法)

    在任意时刻,设已经确定属于最小生成树的结点集合为T,剩余节点集合为S,每次找到最小的一条边(X,Y,Z),满足X∈S,Y∈T。即两个端点分别属于S,T的权值最小的边,然后把点X从S中删除加入到集合T中,并把Z累加到答案中。
    通俗点讲:PRIM算法从任意一个顶点开始生成最小生成树,每次选择一个与当前小树最近的一个顶点,并将这个顶点加入到小树中。然后更新这棵小树到其他点的最近距离。

    具体实现
    1.选用图中的任意一个顶点V0,从V0开始生成最小生成树:
    2.初始化d[v0]=0,其他点的距离值d[i]=正无穷;其中d [ i ] 表示当前这棵小树到其他点的最
    小距离值。
    3. 经过N次如下步骤操作,最后得到一个含N个顶点,N-1条边的最小生成树:
    1>选择一个未标记的点K,并且d [ k ] 的值是最小的;
    2>标记点K进入这棵小树;
    3>以K为中间点,更新这棵小树到未标记点的距离的最小值;
    4.得到最有生成树T。
    时间复杂度为O(n^2),可以用二叉堆优化到O(m log n).
    主要用于稠密图(边数特别多的)

    const int inf = 0x3f3f3f3f;
    int vis[1111];//集合(这里只用到两个集合所以用bool也可以)
    int dis[1111][1111];//用来保存两个点的边权
    int d[1111];//从一点到所有点的最小距离
    
    void prim(int n, int m){
        memset(vis, 0, sizeof(vis));//初始化集合全部不在生成树的集合内
        int index=1;//以1为根节点
        int res=0;//最小生成树边权最小值之和
        vis[index]=1;//将第一个点标进最小生成树集合内
        for(int i=1;i<=n;i++)d[i]=dis[1][i];
        //将现有的从1到所有点的距离放进d中(dis已经先初始化为inf(无限大)再读入的点和边权)
        for(int i=1;i<n;i++){
            int minn=inf;//最小值初始化为无限大
            for(int j=1;j<=n;j++){//遍历n个点找出边权最小值的点
                if(vis[j]==0&&d[j]<minn){//不在最小生成树的集合内并且最小
                    minn=d[j];//将最小边权放进minn
                    index=j;//获取最小边权的点
                }
            }
            if(minn==inf){
                break;//未获得是就是标记完了直接退出
            }
            res+=minn;//将最小边权加入到res
            vis[index]=1;//将该点并入集合
            for(int j=1;j<=n;j++){//遍历1到n个点
                if(!vis[j]&&d[j]>dis[index][j]){//找到不在最小生成树内的点
                //比较是原来的路径短还是加了index的路径短,如果加了index路径更短那么更新路径
                //(很想像短路对不对)
                    d[j]=dis[index][j];
                }
            }
        }
    }
    

    总结,缺少拓展,仍然只会套板子,要学会拓展,多种算法并用解题

    展开全文
  • 最小生成树问题 最小生成树例题

    最小生成树问题

    概述

    • 所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

    最小生成树算法有很多,其中最经典的就是克鲁斯卡尔(Kruskal)算法和 普里姆(Prim)算法

    Kruskal算法

    • 克鲁斯卡尔算法(Kruskal)是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林,图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性(不构成环)的树之间建立连边。

    我们该如何判断添加一条边后是否形成环呢?

    • 要判断添加一条边 X-Y 是否形成环,我们可以判断顶点X在最小生成树中的终点与顶点Y在最小生成树中的终点是否相同,如果相同则说明存在环路,否则不存环路,从而决定是否添加一条边。

    所谓终点,就是将所有顶点按照从小到大的顺序排列好之后;某个顶点的终点就是"与它连通的最大顶点"。

    时间复杂度

    • O(ElogE)或者O(ElogV),其中E代表图中的边的数目,V代表图中的顶点数目。对图中的边按照非降序排列需要O(ElogE)的时间。排序后遍历所有的边并判断添加边是否构成环,判断添加一条边是否构成环最坏情况下需要O(logV),关于这个复杂度等到景禹给你们谈并查集的时候再分析;因此,总的时间复杂度为O(ElogE + ElogV),其中E的值最大为V(V-1)/2,因此O(logV) 等于 O(logE)。因此,总的时间复杂度为O(ElogE) 或者O(ElogV)。

    算法模板

        public Kruskal(WeightedGraph G) throws Exception {
            this.G = G;
            mst = new ArrayList<WeightedEdge>();
    
            CC1 cc1 = new CC1(G);
            if (cc1.count() > 1) {
                return;
            }
    
            //Graph.Kruskal
            ArrayList<WeightedEdge> edges = new ArrayList<>();
            for (int v = 0; v < G.V(); v++){
                for (int w : G.adj(v)){
                    if (v < w){
                        edges.add(new WeightedEdge(v,w,G.getWeight(v,w)));
                    }
                }
            }
    
            Collections.sort(edges);
    
            //判断是否存在环
            for (WeightedEdge edge : edges){
                int v = edge.getV();
                int w = edge.getW();
    
                if ( find(v) != find(w) ){
                    mst.add(edge);
                    unionElements(v,w);
                }
            }
        }
    
    
       public static int find(int p){
            if( p != parent[p] )
                parent[p] = find( parent[p] );
            return parent[p];
        }
    
       public static void unionElements(int p, int q){
            int pRoot = find(p);
            int qRoot = find(q);
            if( pRoot == qRoot )
                return;
            parent[pRoot] = qRoot;
        }
    

    Prim算法

    • 普里姆算法在找最小生成树时,将顶点分为两类,一类是在查找的过程中已经包含在生成树中的顶点(假设为 A 类),剩下的为另一类(假设为 B 类)。对于给定的连通网,起始状态全部顶点都归为 B 类。在找最小生成树时,选定任意一个顶点作为起始点,并将之从 B 类移至 A 类;然后找出 B 类中到 A 类中的顶点之间权值最小的顶点,将之从 B 类移至 A 类,如此重复,直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

    时间复杂度

    • 上面的代码中,当 i == 1的时候,内层的 while 与 for 循环中 j 的取值范围是从 1 到 n-1,内循环一共计算了 2(n-1) 次,其中n为图中的顶点个数;
    • 当 i == 2 的时候,内层循环还是一共计算 2(n-1) 次;
    • 以此类推…
    • i 取最大值 n -1,内层循环还是一共计算 2(n-1) 次;
    • 所以,整体的执行次数就是 (n-1) * 2(n-1),Prim算法的复杂度是 O(n2)级别的。

    算法代码模板

        public Prim(WeightedGraph G) throws Exception {
            this.G = G;
            mst = new ArrayList<>();
    
            CC1 cc1 = new CC1(G);
            if (cc1.count() > 1) {
                return;
            }
    
            //Graph.Prim
            boolean[] visited = new boolean[G.V()];
            visited[0] = true;
            for (int i = 1; i < G.V(); i++){
                WeightedEdge minEdge = new WeightedEdge(-1,-1,Integer.MAX_VALUE);
                for (int v = 0; v < G.V(); v++){
                    if (visited[v]){
                        for (int w : G.adj(v)){
                            if (!visited[w] && G.getWeight(v,w) < minEdge.getWeight()){
                                minEdge = new WeightedEdge(v,w,G.getWeight(v,w));
                            }
                        }
                    }
                }
                mst.add(minEdge);
                visited[minEdge.getV()] = true;
                visited[minEdge.getW()] = true;
            }
        }
    
        // 优化算法
        public Prim2(WeightedGraph G) throws IllegalAccessException {
            this.G = G;
            mst = new ArrayList<>();
    
            CC1 cc1 = new CC1(G);
            if (cc1.count() > 1) return;
    
            //Graph.Prim  改进算法
            boolean[] visited = new boolean[G.V()];
            visited[0] = true;
            Queue pq = new PriorityQueue<WeightedEdge>();
            for (int w : G.adj(0)){
                pq.add(new WeightedEdge(0,w,G.getWeight(0,w)));
            }
            while (!pq.isEmpty()){
                WeightedEdge minEdge = (WeightedEdge) pq.remove();
                if (visited[minEdge.getV()] && visited[minEdge.getW()]){
                    continue;
                }
    
                mst.add(minEdge);
                int newv = visited[minEdge.getV()] ? minEdge.getW() : minEdge.getV();
                visited[newv] = true;
                for (int w : G.adj(newv)){
                    if (!visited[w]){
                        pq.add(new WeightedEdge(newv,w,G.getWeight(newv,w)));
                    }
                }
            }
        }
    

    总结

    • 最小生成树的问题,简单得理解就是给定一个带有权值的连通图(连通网),从众多的生成树中筛选出权值总和最小的生成树,即为该图的最小生成树。
    • 最经典的两个最小生成树算法: Kruskal 算法与 Prim 算法。两者分别从不同的角度构造最小生成树,Kruskal 算法从边的角度出发,使用贪心的方式选择出图中的最小生成树,而 Prim 算法从顶点的角度出发,逐步找各个顶点上最小权值的边来构建最小生成树的。
    • 最小生成树问题应用广泛,最直接的应用就是网线架设、道路铺设。还可以间接应用于纠错的LDPC码、Renyi 熵图像配准、学习用于实时脸部验证的显著特征、减少蛋白质氨基酸序列测序中的数据存储,在湍流(turbulent)中模拟粒子交互的局部性,以及用于以太网桥接的自动配置,以避免在网络中形成环路。除此之外,最小生成树在聚类算法中也是应用广泛。

    最小生成树例题

    import java.io.*;
    import java.util.*;
    
    public class Main {
        public static void main(String[] args) throws Exception {
            Scanner scan = new Scanner(System.in);
            int N = scan.nextInt();
    
            int[][] G = new int[N+1][N+1];
    
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    G[i][j] = scan.nextInt();
                }
            }
            int x = prim(G,N);
            System.out.println(x);
        }
    
    
        static int prim(int[][] G,int N){
            int res = 0;
            boolean[] visited = new boolean[N+1];
            int[] dist = new int[N+1];
            Arrays.fill(dist,Integer.MAX_VALUE);
            dist[1] = 0;
    
            for (int i = 0; i < N; i++){
                int t = -1;
                for (int j = 1; j <= N; j++){
                   if (!visited[j] && (t == -1 || dist[t] > dist[j])) {
                       t = j;
                   }
                }
                
                
                res += dist[t];
                visited[t] = true;
    
                for (int j = 1; j <= N; j++) {
                    dist[j] = Math.min(dist[j],G[t][j]);
                }
            }
            return res;
        }
    }
    
    
    import java.io.*;
    import java.util.*;
    
    public class Main {
    
        static int[] parent;
    
        static class WeightedEdge{
            int v;
            int w;
            int weight;
            public WeightedEdge(int v,int w,int weight){
                this.v = v;
                this.w = w;
                this.weight = weight;
            }
    
        }
    
        public static void main(String[] args) throws Exception {
            BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    
            String[] s = sc.readLine().split(" ");
            int N = Integer.parseInt(s[0]);
            int K = Integer.parseInt(s[1]);
    
            parent = new int[N+1];
            for(int i = 1 ; i <= N ; i ++) {
                parent[i] = i;
            }
    
            ArrayList<WeightedEdge> edges = new ArrayList<>();
            for (int i = 0; i < K; i++) {
                s = sc.readLine().split(" ");
                int v = Integer.parseInt(s[0]);
                int w = Integer.parseInt(s[1]);
                int weight = Integer.parseInt(s[2]);
    
                edges.add(new WeightedEdge(v,w,weight));
            }
            Collections.sort(edges,(o1,o2)->o1.weight-o2.weight);
            int x = kruskal(edges);
            System.out.println(x);
        }
    
        private static int kruskal(ArrayList<WeightedEdge> edges) {
            int res = 0;
            //判断是否存在环
    
            for (WeightedEdge edge : edges){
                int v = find(edge.v);
                int w = find(edge.w);
                int weight = edge.weight;
    
                if (v != w){
                    parent[v] = w;
                }else {
                    res += weight;
                }
            }
            return res;
        }
    
        public static int find(int p){
            if( p != parent[p] ) {
                parent[p] = find( parent[p] );
            }
            return parent[p];
        }
    }
    
    展开全文
  • 最小生成树详解(模板 + 例题)

    万次阅读 多人点赞 2020-10-15 16:04:26
    文章目录1、什么是树2、最小生成树3、最小生成树的应用4、实现最小生成树的两种算法4.1 prim (普里姆算法)4.2 kruskal (克鲁斯卡尔算法)5、总结 1、什么是树 如果个无向连通图不包含回路(连通图中不存在环),.
  • 最小生成树介绍Prim算法简述应用知识点习题: 介绍 个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树(Minimum Spanning Tree,MST)...
  • 最小生成树的构造

    千次阅读 2019-11-06 16:13:18
    最小生成树 树也是图的个特例 什么是生成树? 连通图的生成树是包含全部顶点个极小连通子图,即此树包含图中所有的顶点,并且只含尽可能...2、最小生成树顶点数减1 3、若无向连通图边顶点数1,图...
  • 数据结构学习:图的最小生成树 连通图的生成树是包含图中全部顶点个极小连通子图。 若图中顶点数为n,则它的生成树含有 n-1 条边。对生成树而言,若砍去它的条边,则会变成非连通图,若加上条边则会形成个...
  • 最小生成树

    千次阅读 2017-02-02 15:49:10
    在存在权值相等的边时,最小生成树可能有多个。话不多说,求它个的方法如下:先用Prim生成最小树,同时记录边的关系。用并查集表示//不要压缩路径让每个元素都指向它的父亲节点。找出权值相同的边,去除树上的这条...
  • 最小生成树(Minimum spanning tree,MST)是在个给定的无向图G(V,E)中求棵树T,使得这棵树拥有图G中的所有顶点,且所有边都是来自图G中的边,并且满足整棵树的边权值和最小。2.prim算法和Dijkstra算法很像!!请...
  • 最小生成树:Prim算法

    2021-08-15 19:23:58
    顶点 V0V_0V0​ 出发(图中任何一顶点均可),两个权值边10,11中,其中权值最小为10,将其对应的边(V0,V1)(V_0,V_1)(V0​,V1​)纳入最小生成树 接着从顶点 V1V_1V1​的各边权值 18,12,16以及11进行比较,其中权值...
  • 图的最小生成树

    2017-12-11 20:28:07
    普里姆算法 通过邻接矩阵图表示的简易实现中...算法思想:取图中任意顶点V作为生成树的根,之后若要往生成树上添加顶点W,则在顶点V和W之间必定存在条边。并且该边的权值在所有连通顶点V和W之间的边中取值最小
  • 1、生成树和最小生成树 1.1 生成树 连通的无圈图称为树,就是不包含循环的回路的连通图。 对于无向连通图,生成树(Spanning tree)是原图的极小连通子图,它包含原图中的所有 n 个顶点,并且有保持图连通的最少的边...
  • 个连通图的生成树是个极小连通子图,它含有图中全部顶点,但只有足以构成棵树的n-1条边。 当用联通网来表示n个城市以及n个城市间可能...(1)编写Kruskal算法代码,实现图的最小生成树求解,且输出最小生成树
  • 1. 最小生成树(又名:最小权重生成树)概念:将给出的所有点连接起来(即从个点可到任意个点),且连接路径之和最小的图叫最小生成树最小生成树属于种树形结构(树形结构是种特殊的图),或者说是直链型结构,...
  • 最小生成树最小生成树(minimum spanning tree)是由n个顶点,n-1条边,将个连通图连接起来,且使权值最小的结构。最小生成树可以用Prim(普里姆)算法或kruskal(克鲁斯卡尔)算法求出。我们将以下面的带权连通图为例...
  • 图的应用——最小生成树

    千次阅读 2019-12-30 14:25:02
    最小生成树最小生成树构造最小生成树的准则贪心算法(Greedy Algorithm)Prim(普里姆)算法算法思想 —— 归并顶点算法设计KrusKal(克鲁斯卡尔)算法算法思想 —— 归并边算法设计Prim和KrusKal比较 最小生成树 ...
  • 6、求最小生成树,普里姆(Prim)算法

    千次阅读 2020-03-08 10:26:16
    1生成树一个连通图的生成树是它的极小连通子图,在n个顶点的情形下,有n-1条边。生成树是对连通图而言的,是连同图的极小连通子图,包含图中的所有顶点,有且仅有n-1条边。非连通图的生成树则组成个生成森林;若...
  • 最小生成树 Floyd算法O(n^3)- 动态规划 思路 f[i, j, k] 表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1], f[i, k, k - 1] + f[k, j, k - 1]) 读入邻接...
  • 无向图最小生成树的Prim算法实现 前言 本文讲解最小生成树的定义及实现原理,并根据...最小生成树是图的所有生成树中的棵权值(树中所有边的权重之和)最小的生成树 三、生成树性质 用条边接树中的任意两个顶点都会
  • 最小生成树算法之Prim(普里姆)算法

    千次阅读 2021-07-20 17:13:08
    最小生成树的可以通过Kruskal(克鲁斯卡尔)算法或Prim(普里姆)...第步:设图中所有顶点的集合为V,u代表已经加入最小生成树顶点的集合,v代表未加入最小生成树顶点的集合,最由于从某点s开始,因此u={s},v={V-u}
  • 1 图的最小生成树定义及相关约定 图的生成树:图的生成树是它的个含有其所有顶点的无环连通子图。 图的最小生成树:图的权值(所有边的权重之和)最小的生成树。 约定:最小生成树只存在于连通图中,如果图不是...
  • 连通网的最小生成树

    2021-12-01 17:16:25
    什么是连通网的最小生成树个含有n个顶点的连通图中,一定可以选出n-1条边构成个极小...有个网得到其对应的最小生成树的算法有两种,克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。 克鲁斯卡尔(Kruskal)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,769
精华内容 11,107
关键字:

最小生成树是顶点数减一