最小生成树怎么画

crosco 算法用于求图的最小生成数，目标是在连接所有节点的前提下，让加入的所有边权重总和最小，并且整个结构不能出现任何环。基本思路很直观，先把所有边按权重排序， 再从小到大依次尝试加入生成数。第一条权重为一的边直接加入，接着处理两条权重为二的边，根据存储顺序加入其中一条即可 立条。权重为二的边若会形成环，就必须跳过，避免重复连接。 继续处理权重为三的边可正常加入。 权重为四的边加入会导致环，因此跳过 之后权重为五的边可放心加入。当所有节点都已连通，算法随即结束。记住关键点生成数最终一定只有 b 条边，其中 b 等于节点总数减一。 为了检测是否可能形成环，我们把图中未联通的部分看作不同集合，不同集合代表彼此暂未联通的节点群。若两个节点在同一集合中，说明它们之间已有路径相连。 当给 x 和 p 连边时，需要合并它们所在集合。 给 q 和 m 连边时，也要做同样的合并操作。 如果此时尝试让 p 圆连边，就必须先判断它们是否已在同一集合内。 若发现 p 和 n 属于同一集合，这条边就会形成环，必须跳过。若属于不同集合，则可以安全加入。 crosco 算法主要的额外开销来自排序与查集合。排序所有边需要一 logi 时间一维边数量环检测，借助并查极完成并查极地查找近似常数时间。它的复杂度通常记作 alpha v 增长极慢，因此整体时间主要由排序决定， 总时间复杂度可视为一 logi。 空间方面包括临街表占用的 v 加 e 空间、 排序后的编辑占用一空间，以及赋节点表与质表占用的微空间。总计大约为 v 加一量计。

假设你用的是红色，先画第一棵树，那你明显只能画一个根结点是红色的， 你会发现你没办法再画第二棵树了，因为第二棵树你最多画两个节点，你重画一个红色的节点的话，那跟第一棵树一样，那肯定不行。如果你画两个红色节点的话，那也包含第一棵树也不行。所以游戏结束你只能画出一棵树，那我们知道去一就等于一。 接下来我们来玩玩看。吹啊，用两种颜色，比如是红色和绿色，那你第一棵树比如还是用红色画一个根结点。 第二棵树如果你用绿色画一个根结点，那你会发现你第三棵树就没法画了，因为第三棵树无论怎么画，必然包含第一颗或者第二棵树。但我们还有一个 更好的做法，就是第二棵树化成绿色的根结点，接着一个绿色的叶，这样我们第三棵树就可以画成只有一个绿色根结点的树就一个根。因为我们规则只限制后面的树不能包含前面的树，没有规定前面的树不能包含后面的树。 这样虽然我们第二棵树包含了第三棵树，但是第三棵树没有包含之前的树，所以这是允许的。 这之后你就会发现你再也无法画出第四棵树了，所以吹二等于三。好了，吹一吹二的游戏我们都玩过了，现在到见证奇迹的时刻了，我们要玩吹三了。 比如你可以再加入一个颜色蓝色，用红绿蓝三色来玩这个话术的游戏，你会发现这次你似乎发挥的 大多了，你可以画非常多的数。我在节目介绍里也放了 t 三游戏开始的十二棵树的可能的画法， 但是我劝你不要继续了，因为你无法划到他结束的时刻，因为这个翠三的值实在太大了，大到惊天地泣鬼神，比蛤蜊横竖还大。 当然，你此时可能会质疑，你怎么证明 t 三是一个有限值，而不是无穷大，也就是我可以无穷的玩下去呢？ 这里要用到一个定理，叫克鲁斯克尔数定理。克鲁斯克尔这个名字计算机系的听众太熟悉了，克鲁斯克尔算法是考试必考的对不对？ 克鲁斯卡算我们计算机系学生膜拜的大神，他已于二零一零年趋势，这里我们也顺带缅怀一下。今天我们 不考最小生存数算法，而是克鲁斯卡尔发现的这个数定理。这个定理有个粗糙，但简单的说法就是，如果你给我无穷多个数，那其中必然有一棵树是另一棵树的英孚 ambulable 就是下确届意义上的嵌入，那 t 三是一个有限的数，其实就是这个定理的直接推论了。

同学们大家好，我是蚂蚁期末团队的肖老师，本节课由我来继续讲理散数学期末突击课，希望大家期末考试不挂科。而本节课得到了讨论最后一部分内容，这部分涉及到凶恶力算法， 最小数以及最小生成数，最佳分，最佳最好的全数笛士特斯拉，还有那个判断二分图的那个饱和和非饱和的对齐问题，以及最后的判断平面图的问题。这节课涉及到小细碎点比较多，这也是图论的特点。而本节课我们来继续讲以下内容。 首先我们可以看到无限数就要生成有限数，二分图，平面图这些东西又是有很多的概念，我们来一个一个讲。首先无限数，何为无限数？我们可以看到没有循环的无限连通图称为无限数，简称数。 就比如这样我就没有一个循环，而这样我也没有一个循环。说我怎么样循环能，能能到到我的点还是怎么样的呢？对吧？ 没有循环的无限连通图，这又是循，这又是树，而树中度为一的顶点为树叶，这就是这个即度为一的顶点，而度大于一的顶点，比如说这个 内点，它就被称为内点。而森林就是没有循环的无向图，称为森林，森林中每一个点头分支都是树，这就是说我们这就是无向数和森林的概念。而我们的树还有以下性质，树中任意两点有且仅有一条路径相连，我们可以看到了。 而数中有 n 个定点和 m 条边有这样一个公式，这个公式很可能计算题会用到 n 等于 m 加一而数如果任意删提一条边，则变成不连通图，说明该数是连通成了最小的图， 而数中任意两个不邻接的丁点中添加一条新边，则构成图。构成图包含维一的循环，比如说我加这个，则构成了一个循环，大家就可以看到了。而 我们现在要解释的是我们该如何去 进行一个习其的训练。而还有一个概念是生成树，生成树就是既是五项图，由它的一个紫图生成的，它的一个紫图是一棵树，则它就称为生成树，就这么简单。而最小生成树，我们就是在生成树中找一个最小生成树， 就是 crystal 算法，我们可以看到最小乘除数的算法，我们可以这样看，我们把记中的个别按全值大小排序，就是说我们会排序，比如全差一二三四五，我们按全大小排序，然后初值化一个空集，这个空集初值是什么都没有的， 我们以下步骤，直到包含 n 减一条边，比如说我们首先我们要选择全是最小的一条边，这个就是一，然后我们要看继续往进加全是最小的边，而我们看这个边能不能构成环路，如果不构成环路，我们加下去构成环路，我们就把它剔除，这又是 crystal 算法，我们来一个一个解释， 我给大家画了一个图，这又是一个无向图，而此时我们要对它进行一个 crystal 算法的演练，首先我们把它权重排起来，即这样排起来了，我们出场一个空集 s， 我 们首先把最权重最小的 b c 放进来，比如 b c 在 这里， 而在 b c 放进来后，我们在接下来的地方，我们再选择一个最小的，也就是说我们要选择 a、 b， 即把 a、 b 选择， 那我们要再接下来再选择，我们再把 a、 b 和 b、 c 都去掉，我们要在剩下的 a、 c 到 c、 e 中再选一个最小的， 那我们看到 a、 c 实际上它已经跟我们选好的 b、 c、 a、 b 构成了一个循环。哦，这是万万不行的，那我们 b、 c 就 不，那我们的 a、 c 就 不加了呗，那我们就哥，那我们就加，继续剩下最大，那我们就加个 b、 d、 b、 d， 不 构成循环， 那加了以后， b、 d， 我 们再剩下的，我们再选一个，我们能选 c、 d 吗？因为我们的 b、 c、 b、 d 跟 c、 d 会变成一个循环了，所以我们不选 c、 d， 我 们剩下再选，我们就要选 d、 e， 而 d、 e 选择完以后，我们看是否要选选择我们的 c、 e 呢？答， c、 e 和 dc 在 c、 e 的 c、 e 我 们是否能跟它，就是源于这些图的基础上，我们是否可以和它进行一个， 进行一个全直，进行一个，变成一个循环呢？我们可以看到 c、 e、 b、 c、 b、 d、 d、 e 它们构成一个循环，它们四个边构成一个循环，那我们万万不能加了 b、 c、 b、 d。 第一，要如果加 c 的 话，它们就构成一个循环，那我们只有这四个，所以说这又是我们的 s。 而最下的步骤，我来告诉大家严格的写，你说这样写，首先先选这个，加入 bc， 然后不会不形成环路的前提下，我要加入 ab， 在 此之上我如果加入 ac 的 话，我会形成一个循环，我不加 ac， 在 此之上，我选择 b、 d 全值， 而加入 b、 d， 我 并不会形成环路，我可以加，再加入 c， d， c， d， 我 又变成环路了，我又不加，再加 d， e， d， e 不 够是环路，我加进去再加 c， e， b， c， b， d， d， e， c， e 构成环路的，那我就不选了。所以最终我的最正确的编辑是这样的， b， c 就是 bc， 这是 ab， 这是 b、 d， 然后这是 a， b， e， 这是一个数， 我们可以看到这个数就是这样子一个形式，而最小数的全值总和就把他们全加起来，一加二加四加六等于十三，这就是无限数与最小生成数的整体算法。算法并不难，大家需要严丝合缝的按照我这个步骤去一步步执行下来，这就是无限数中的知识点。 全图的最小生成数问题跟大家分享完毕，好进行下一个知识点。有项数，有项数，就是有这个方向的一个数嘛。 满足以下条件的有效图，这行有效数它久写，仅有一个入度为零的顶点，称为根，就是这个部分入度为零，除根外，其他填入度都为一。那很明显， t 中每一个顶点都有一条该顶点跟到该顶点路径，当然跟到哪都能到达呀，这就可以啊。而接下来我给大家弄了一个有向数的图，要跟大家说这些概念，首先父子关系，这是我们的 t 有 向数， a， a， b 乘以，如果 a 是 实点， b 是 终点， 则称 a 是 b 的 父亲。要是我十点引申出一个中点，那我就是你的父亲，而 b 是 a 的 儿子。如果 t 中有一条以 a 为十点，以 x 为中点，有向对称，则称为 a 为 x 祖先， x 为 a 的 后代。可以看到，这个题中十五就是六的祖先，是九的祖先，而九和六是十五的后裔数和内点。出度为零的点称为树叶或叶片，就是一二三、四、五叶片， 其中其他顶点称为内点或支点，这就是根据这个图前树叶内点以及父子关系的描述。 而接下来层次和高度，从树根的顶点到的的路径长度称为 a 的 水平和层次，树中最长的长度称为 a 的 高度，这就很明显可以看到。 而 a 是 t 中的一个顶点，由 a 导出的所有点都是包括 a 的 后移导出，所有点都是其它的， 都是它的有效图的指数，那么 a 是 指数，就十五导出的这些所有点都是它的指数，这就是它的概念。 n 元素，即每个顶点都有 n 个儿子，也就是每个顶点引出两条线， 而特别的 n 引出 n 条线，特别的如果每个点都引出两条线的话，那么称其为二叉数，这个就是二叉数，每个点都引出两条线，这是树叶啊，树叶就不再引了。好，这是所有概念，这是跟大家分享的， 大家要明白了，这些是最基本的概念，大家要跟针对这个图去衡量，其实很简单，就是一个父子关系，高度关系等等等。而此时完全 n 元素，也就是每个每个点引出 n 条边的内点数和叶片的关系，叶片就是这些东西，而内点数则是 除那个树叶和叶片以外的其他点，称为内点或支点，它们这有这样一个公式，这个公式就不细讲，大家如果有计算题的话，自己用一下，我们的重点是要讲如何找到最优数， 并且使这个完全二叉数有最小的权。首先代权数，我们要找到完全的二叉数，我们每一个东西都有权重，如果一棵树叶的权重是这些为二叉数，那我们 如果他权重最小的话，那我真是称此数为最优数。而最优数的求解依赖于一个算法叫哈夫曼算法， 把树叶权这些排版看了，然后让他最从小到大依次排列，将权最小两个合成一片树叶，并把它们看成一个整体，继续与他排列，这是最优数，直至最后只剩一个 wi 的 集合，那就完毕了。 那我们来看一下，看一下这个哈夫曼算法，求最优数，首先我们来这样看，我们有一二三四五五个点，首先我们从大到小排就完序了，我们要合并最小两个，他俩就合成三 三四五， ok， 他 俩又合成最小的，变成六级，接下来变成六四五六四五中两个最小的号，他俩最小合起来就是六九六九，他俩合成最小就是十五，这又是他的一个算法的过程， 而我们如何根据这个算法过程把这个数画出来，这就是接下来要讲的东西。这个过程是非常简单，就是不断的合并这两个最小的，直至变成最终的一个。 所以我们就可以看出我们一二三四五一和二首先变成了三 二，接下来的三和三，我们要把它再给它弄上，就变成了六二，接下来的六，接下来四五，我们合起来就是九，接下来六和九合起来就是十五。你可以看到我这个数的结构形式和它是完全一样，只不过它是， 它是根据我把我这个数像是这个数，像是歪脖子，把它给正过来，写成一个规整形式，这就是我的最优数的图解和我的最优数的求和方法， 就是这样做的，大家一定要严格按照我的步骤去一步一步执行下来。再重说一遍，一二合成三，三和三，再合成六，六和六，剩下四五合成九，六和九，再合成十五。看跟这个图完全一样，这个是我们的哈佛曼算法，我们讲了两个题已经一个是这个角 cross 算法以及哈夫斯曼算法，哈夫曼算法这两个都是有可能考大题的，大家要注意，无论是图和过程都要会弄，就是有项无项数一个题，有项数一个题。接下来二分图还有一个题， 我们可以看到和为二分图，我们就将顶点的集合 v 化分为两个子集， v 一 v 二， v 一 交。 v 二等于 v， v 并二等于空集集，使图中的每一条边的一个端点在 v 一 中，另一个端点我在 v 一 中，这是 v 一 端点，这是 v 二端点，就是如此。就是我把点集划分成 v 一 v 二，其中 其中每一条边的一个端点在 v 二中，仅此而已。它这个题中， a 一、 a 二、 a 三、 b 一、 b 二，它们构成了所有的边，即我 a 一 a 二在 v 一 里， b 一 b 二在 v 二里，就是我的 二分图。而接下来简单二分图，还有个完全二分图，就是我每一个点都要和所有的另一个，比如说我 v 一 是 a 一 a 二， a 三跟刚一样， a 二是 b 一 b 二，有时候我 a 一 的点必须要跟 b 一 b 二点， a 二点必须跟 b 二点， a 三点必须跟 b 二。有时候我每个点都需要跟另一个集合中所有点相连，而这个图就是我们的二分图，它为记作，记作 k 三。二就是我们的完，就是我们的一个完全二分图，即其中一个集合 点，要把每另一个几何的每一个点之中都要进行一个连线，这又是我们的完全二分图。而判定方法则是判断它是二分图的重要条件，就是图中每条循环都有偶数边组成，这个是双条件，大家可以用它来判断是否为二分图。 而二分图之中还有个题型叫对齐的匹配，首先我们可以给他规定， a 一、 a 二、 a 三、 a 四、 b 一， 然后 b 一， 然后给他再列这是 b 二，接下来是 b 三，接下来是 b 四。 好，我来给大家换一个图讲，因为这个图写起来会更加清晰简单，大家要注意一下，我换了一个图，这个图已经标注好了，给大家， 我们先补全，这是 a 一、 a 二、 a 三， a 四和尾对齐呢？就是 m 中两条边没有公共的端点。比如说我这个题中的 a 一、 b 二和 a 二、 b 三，它们标红的这三条线，它们就没有公共的端点，它们各自端点 都没有一个公共的，他们的起点和终点他们都没有相交，这又是他们的一个对积，则对积 m 就是 这三个边， a 一、 b 二， a 二、 b 三，然后 a 四、 b 一 看他们，他们的起点中间都没有一个重合，这就是对积。而我们乘点，而 如果 v 是 某条，如果 v 是 m 中某条边端点，则称它是饱和点，并称 m 是 饱和的，否则 v 乘 m 是 非饱和。在我们这个题中，我们这个里面所需要所有东西， a 一、 a 二、 a 四、 b 一、 b 二、 b 三是饱和的， 而剩下的点 a 三只有这一个 a 三没有红线引出来，则它就是非饱和的，就仅此而已。一个概念，饱和点就是有设计到 m 的 点，不饱和点就是这样的，那我们可以给它进行一个， 这就是给它进行一个定音，大家要明白。而最大对积就是说我这个对积里面的数不能再大，就是对积里面的边数不能再加。比如说我这个题， a 一 b 二， a 二 b 三，它也是一个对积，但是它不是最大的对积，因为最大的对积还有一个 a 四、 b， 仅此而已，就是最大对积。 就这个图中再也没有能听下去编，让它再变成对积了。然后我们要介绍两种路径，这个一会算法有用，是它是二分图， m 是 对积， p 是 记成一条路径。如果 p 是 由属于记成属于 m 的 边和不属于 m 的 边交替组成的，则称为交替路径。就是说，比如说这个图，就是说我红蓝相见，就是我先红再蓝，先蓝再红，这种就是叫交替路径，即属于 m 的 边和不属于 m 的 边，我都给它交替。 而我们的交替路径是这样的，十点、十点和中点都是 m 的 非饱和点的交替路径，称为 m 的 增长路径。也就是说我十点和中点都必须是没有任何红线的点，这就是它的增长路径。 所以可以看到 m 的 增长路径必有计数点标。如果我十点是蓝色的，它发出了一条蓝色的线，那我下一个接上一个红色的线，然后我的终点还需要是蓝色的线，那我必须要接上一个蓝， 这就是它的增长路径。增长路径就是说我起点和终点必须是非饱和点，而我的交替路径则不需要这样。 而知道这些定义，我们才能进行匈牙利算法求解。我们接下来我们就要看到给定一个二分图，另 m 是 任意一个对称，也可以是直接是空的，你能找出来就找出来，找不出来你直接弄成空的， 如果 u 一 属于 v 一 这样，所以这些东西大家不用看，我来给大家一个一个讲解，一点一点的给大家讲解。首先你可以看到这个图，我可以明显看到这三条画红色的边，我给他编个号， a 一， a 二， a 三， a 四， b 一， b 二， b 三， b 四，然后还有 b 五，你可以看到，首先我可以看到这三条红色的边，它完完全全它就是没有任何交点的边，就是说它们没有任何交叉的点在一起，则它们就是对齐， 而我们如何来求最大对集呢？首先我们要找到图中的非饱和点，我们来找啊，有没有红线的点，哎，他没有红线，他没有红线，哎，他没有红线，比如说剩下的点 我们都可以去给他找一下，我们对每个点进行一个一个渲染算法应用，就可以得到它最大堆积。那么首先我们需要先看到 a 四点，那么在 a 四点中我们可以看到 a 四点，它的起点，它的起点是它是非饱和点，它是一个蓝线，我也说我们不知道这根线到底就除完红，除了红线以外都是蓝线，我们并不知道，事先并不知道它是否有红线的情况下，我们就不能 鲁鲁莽认为它就是红线，我们直接这样，我们一样非饱和点，饱和点交替，你可以看到这样就没有从它引出的路径，就没有办法交替了，因为它引出的路径 它就只能是蓝线，蓝线，蓝线蓝线都是蓝线跟蓝线不行啊，得蓝红交替啊，先蓝再红，最后就开始必须是蓝，最后也必须是蓝才行，那这样就不行了，那我的 a 四点我就不能用了，把它抛弃掉线， 那我看到我的一个 b 点哦， b 点起点哦，它从 a 点起点可以吗？可以的， b 一， 先从这里它有个路径，就是 b 一 蓝线红，就是这样子，我用激光笔给大家解释， b 一， 首先蓝线红线，然后又蓝线哦，你就可以看到这个路径是可以的，我们不妨直接给它标记一下， 也就是说此时我们的 b 一 蓝线，红线蓝线，我们就这条路径，我们就认定了，而我们是我们认定了这条增长路径以后，我们现在要做的就是让这条路径让所有线红色的变蓝色，蓝色的变红色，也就是说现在 我们这条线要变红色，而这条线也要变红色，而我们刚刚中间这条红线它要变成蓝色的了。 而此时我们再看现在这个图，我们我们只剩下 b 四唯一一个 b 四的点，我们去我们只剩下唯一一个 b 四的点，我们看能否去给它找一个交替。首先 b 四 只剩下 b 四这个 c 饱和点， b 四我们看能不能 b 四，我们这条蓝线横线，蓝线横线蓝线，这都是便利了我们这些东西的，没有任何意义，而 b 四这样它没有办法交替， 所以说我们就可以看到 b 四这个点，我们我们 b 四这个从 b 四出发的这些点，我们都找不到最大的路径，所以说 这个题目我们就到此为止，解释完毕。我们最终找到的也就这四条红线，也就是我们的对集， 此时我们可以看到我们的 m 集合，就等于此时的 a 一、 b 二， a 二、 b 三， a 四、 b 五，还有 a 三 b 一， 你可你可能会说，为什么 b 四，你明明 b 四有路径，为什么不继续弄了呢？因为我们现在我们可以看到我们的 v 一 的集合， 他到此为止，他都满了，就是他，他每一个边，他，他每一个点都已经有红线牵出去了，就是每一个点，我最多最多就是这些线，所以你可以明白， 所以每一个点，因为我保证他不相交情况下，我每一点最多就引出这些线，如果我一个点引出两条线的话，那不就相交了吗？那不就不符合了。我既然每个点都变道，并且有一条线， 那我就已经满足条件了，即我得到这个，而不需要考虑下一个，只需要其中一个 v 一 或者 v 二，他满足的，那么就可以了，那么他就可以作为我们的一个 最大堆积，这就是我们最大堆积最终的求出来的结果。 ok， 接下来是平面图，如果能一个把这个图画成端点以外，任何两条边都不相交，则是可平面的 完全图，它是非平面图，完全二分图都是我们前面讲过的，它完完全全它是非平面图，这两个图非常重要，考的时候可能会考到，可以看到这个平面除了端点以外，没有任何两条边相交，可能这个平面图你就要说它不是有两条边相交吗？哦不，你说的是端点，它其实这个图可以这样画， 它其中这两个线，这样这就是它的一个图， 它其实是平面图，你要会这样拉出来，把这根线给它，把这根线给它拉出来，这就是平面图。而这个明显是非平面，你这些线怎么拉它都会有交集的。而区域则是这样子区域，比如说我来一个 这个区，我 r 一、 r 二、 r 三，除了 r 一、 r 三以外是 r 四区域，就是我有这四个区域，这就是区域的概念， 而区域的概念会帮助我们进行以下的内容讲解。设计为五项联通平面图，它有 n 个点， m 调边、 r 区域，它们有这个固定的公式，这个公式可能考分，考到你要去记住。而判断是否平面图的方法一个重要条件就是 它的不高开二度同构的 k 五和 k 三三，所谓同构，就是它们点和点之间的关系一样，无非就是显示的情况不一样。而推论则是途径是这样，则三 n 大 于六 m， 这是其中一个推论，这这个推论 如果它平面图的话，它则有这个推论，这个推论可以帮助我们解决，帮助我们判定一下它是否为平面图。 而且平面图步骤你不需要管这个，这个是乘法，你只需要看这两个是否检查边和顶点关系，如果满足的话不一定，如果不满足的话就可以推出来，那么它一定不是平面图，还要检查子图，看，同时包包含这种 k 五五和 k 三三的子图， 比如说这个，这个图，你觉得它是平面图吗？其实这个图和这个图是同构的，那为什么同构呢？你把 b 点给它拉下来，则你就这样拉 e、 d， 这是 f， 这两个是 c 和 v， 你可以看他们边跟边，点跟点之间边的关系完全没有变变，也就是说它的一个形式，所以它包含 k 五、 k、 k 三三，所以它不是。好，这又是平面图，一个知识点，就这里严格记住这两条就够。 而这就是我们所有讨论的内容，可能有些点没有讲到，但是已经尽可能的在三个小时把所有的点都涉及到了。 而对齐部分的题目大家要注意，因为考试它会考，所以这就是本节课的全部内容。本节课我们再来理一下我们本节课讲的哪些东西，因为这节课内容还是蛮多的。 首先有项数，有有项数，这里有个最小分寸数的问题，求解，有项数，这里有一个最小全数的求解。二分图，这里有一个那个度，那个 增长路径，求最大对极，最大对极的题目出现。平面图有个判定，平面图的两条定义存在，所以这四个题都有可能出现大题，大家要好好的明白它的两条定律存在，所以这四个题都有是图的五个大题之中的其中之一。好，本节课内容到此结束。

大家好，这个视频呢是关于最小生存数的第三个视频。嗯，在这个视频里呢，我想谈谈 blem 算法在编程的时候所涉及到的存储结构。 我们先来看一下普利姆算法的算法描述，嗯，他这个算法呢是从一个点开始的，我们首先呢把一个顶点加入到这个最小生成数中，我们这个最小生成数就叫 mst， 那么这个时候呢，我们就把数上的点 放在一个优集合中，竖下的点放在这个 v 点优集合中，这个 v 是所有顶点的这个集合。 嗯，为了便于讲解哈，我就把树上的点全部标注成红色，树下的点呢标注成蓝色，这样的话，这两个集合我们就一个叫红点集，一个叫蓝点集。那么第二步呢，就是找什么呢？跨越两个集合的边，也就是说一头 是红点，一头是蓝点的边，我们做一条线把这两个集合分开，那么这个时候这根线切割到的边就是我们要找的边，那么这里最小的是哪一个呢？是这个， 我们把这条边加进来，这个时候呢这个红点就有了两个点，我们继续， 这个时候哪条边最小啊？这条边最小，这个时候红点极就变成了三个点，那么继续呢，我们就可以完成他整个的 这个操作，当所有的点都变成红点的时候，这个算法呢就结束了。嗯，那么刚才的这个算法过程，如果我们从编程的角度怎么样设计他的存储结构，实现他的算法呢？我们看这里 首先怎么样存储这个代全联通图呢？我们在这里呢就采用常规的这个临街矩阵的存储方法，这里呢我们就用一个二维数组来存放这个临街矩阵，这个行坐标和列坐标分别就代表这个顶点的这个编号，那么如果两个点之间有边相连，我们就把它的全值 填在这个地方，如果要是没有边相连的话，我们就填无穷大，自己到自己呢，我们认为是零，所以呢这个主对角线是零，因为这个是一个无向度，所以呢这个矩阵呢是一个对称的。 嗯，接下来的一个关键设计，就是我们在这里头设计一个结构数组，用它来存放我们代选的边，嗯，当这个叠带完成以后，这个里头的边就全部变成了这个最小生成数上的边，这个数组的长度呢是跟这个顶点的 这个个数是相关的，我们用它的下标代表一组顶点，那么这个里头每一个元素呢包括两个玉，一个呢是存放它的临结点，一个呢是存放的这条边上的这个全指。 由于一开始我们的这个红点集里头只有一个零号点，所以呢我们所有的代选的边一定是跟零号顶点相关的。我们就把这个矩阵里头这个低行数据，低行数据是什么？就是零到所有顶点的数据，我们就把它抄到这个地方， 对吧？这个连接点呢全部都填零，这个时候我们这个代选的边六幺五，大家看就出现在这，那么这个两个无穷大是因为零到四和零到五没有变，所以这边是无穷大，那么我们比较最 小就是挑什么呢？就是在这个里头进行比较，注意我们指比较大于零的数，这个等于零的数我们不算好，那这里头比较的最小是谁呢？就是一这个，也就是说这条边， 我们就把这条边加入到这个最小生成数中，那么这边做一个什么处理呢？我们说这个二 零这条边已经被选中了，已经被选中了就意味着什么呢？后面呢他的这个大小不再参与比较，那我这个地方做一个什么处理呢？因为我们后面这个大小比较的是对全值大于零的进行比较，所以呢这个地方我们只要给他改成负一， 就不再参与后面的比较。呃，题外话讲一句，那么有些程序在这个地方，因为他的这个大小的这个比较 条件是对非零的这个全职进行比较，所以呢他这个地方呢就要改成零，改成零以后呢，那么他的这条边的这个全职的信息就要回到原来的这个句子里头去找 啊，我个人更喜欢这种方式。好，接下来呢，我们说这个代选的边，那么现在二加进来以后，那么代选的边呢，就变成了这个 六条，实际上呢加上这个零到四和零到五应该是八条。我们看对于这个蓝点， 每一个点因为跟零和二都可能产生边，实际上呢应该是每一个蓝点呢，都应该是有两条边，那么这边呢为每一个蓝点呢，他存放的这个边呢，只能是一条边，那这时候怎么办呢？很显然我们就把什么呢？ 小的那条边放过来，那么小的那条边就是什么呢？就是用二，就是用这行数据，二到所有的顶点的值和什么呢？和当前的这个是 零到所有顶点的值进行一个比较，把小的放进去，我们只比较这个大于零的数，大家看这边五比六小，对吧？把这个替换进去，这个因为是从二点过来的，所以这个改成二， 这个是五，这个是五，一样的我们就不动了，这个是六，这个是无穷大，很显然要改成六是从哪个点过来的？二号点，这个呢是四， 这也是二号点，所以修改以后呢，这个结果呢就变成了这样， 后面呢就一样处理了。好，我们继续看。那么现在这个最小的是谁呀？是这个四，那么也就是说五二这条边把它加进来。 好，那么加进来以后呢，这边要做一个什么处理呢？嗯，这个把这个式呢就改成一个复式， 同时因为加进来五号点，我们就把这行数据和这行数据再进行一个比对，把小的替换进来，嗯，这个是二比五小，对吧？所以这个地方要改成二，这是从几号点过来的呢？是从五号点过来的， 这个是一样的，那这个时候呢，数据呢就变成了这样。好，我们继续。这时候最小的是谁 呢？是二，也就是说把三五这条边加进来。好，那这个时候呢，我们就把这个二改成一个负二， 因为加进来是三号点嘛，把三这行的数据和这行数据进行一个比对，这个是无穷大，这是无穷大，比这个大，那就不用替换了，我们看一下， 现在只剩下五六了，哪个小啊？五小，我们这个时候就把一二这个边加进来，我们看一下， 那么这边呢就把这个五变成负五，这个顶点是一，对吧？我们就把这行信息再和这行信息进行一个比对，实际上只剩下这一个位置了哈，那么三比这个六要小，所以把这 这个地方换成三，这是从哪个点过来的呢？是从一过来的。好，那这个时候呢，这个数组信息就变成了这样， 最后只剩一个点了吗？当然就是他，我们就把这条边四一这条边加进来啊，这个地方呢就给他变成一个负三， 这时呢这里头所有的边就变成了一个小于零的边，那么这个算法呢就结束了。那么我们最后看一下这个最小深层数里头的几条边是什么呢？大家看就是一二，这个全值是五二零，全值是一三五，全值是二 四一，全值是三五二，全值呢是四无条变算法借数。好，关于最小生存数的三讲呢啊，我就介绍完了，感谢你的收看，我们下次见，拜拜。