废柴日记4：迟到的『构造最小生成树算法』①

本文主要是介绍废柴日记4：迟到的『构造最小生成树算法』①，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

=================================================

废柴日记4：迟到的『构造最小生成树算法』· 其一

=================================================

日期：2021年9月14日天气：晴

=================================================

其实，我每天都还好。

昨天还一脸自信的样子，嚣张地说着什么 “根本不需要我去想该更新什么内容” 的话，结果迅速打脸，有种吃瘪龙的感觉。

就在博主还在发愁该如何守护日更的誓言，正大光明的水（gan）一篇博客出来的时候，博主突然想起来，我还欠数据结构老师一篇关于普里姆(Prim)算法与克鲁斯卡尔(Kruskal)算法讲解的博客。

那还是一个阳光明媚的下午，当时我们正在机房上实验课，上机的内容正是普里姆(Prim)算法与克鲁斯卡尔(Kruskal)算法。之前也说过，博主的脑回路相较于常人比较的特别，我对于这两个算法的逻辑有着独特的理解方式。

实验课下课之后，我又去找老师讨论一些东西。不知道是怎么了（现在想想就是当时脑子抽了），我突然说了一句：“我感觉我可以把我对这两个算法的理解写成博客，这样的话也可以让更多的人了解到这两个算法还能这么想。”

当时是大二上学期，现在已经是大三了，我也算是拖欠了1年左右。

但是，答应别人的事，无论多晚也要完成，绝对不能辜负这份信任的。

"拉过勾的事情，就一定要做到！"——《星游记》

所以这也算是填坑吧，接下来的几篇『废柴日记』，博主将会用尽毕生所学，尽全力向大家描绘我脑中的『最小生成树』宇宙。

前方高燃，闲人回避。

Ⅰ.概念引入（图，无向图，有向图，网）

首先，在引入最小生成树这一概念之前，我们需要学习它的几个前置知识：

①图：在计算机科学中，图就是一些顶点组成的集合，顶点与顶点之间有边相连，如下图所示。

我们将上图命名为图 G ，则在图 G 中共有5个顶点：{1，2，3，4，5}，在这5个点之间存在着5条边：{1→2，1→5，2→3，2→4，3→4}。

我们再将由顶点组成的集合{1，2，3，4，5}命名为 V ，由边组成的集合{1→2，1→5，2→3，2→4，3→4}命名为 E ，则图 G 可以表示为：G=（V，E） 。

图的概念非常简单，大家可以联想一下初中时所接触到的几何图形。
（比如一个三角形，它就是由3个顶点与3条边组成的图，只不过我们当时研究的是如何在那个三角形上画一条辅助线然后解一大堆式子才能从老师那里拿到第二问的分数罢了(lll￢ω￢)）

②无向图、有向图与网

无向边：若顶点 Vi 与顶点 Vj 之间的边没有方向，则称这条边为无向边，并用无序偶对（Vi，Vj）表示。
有向边：若顶点 Vi 与顶点 Vj 之间的边有方向，则称这条边为有向边，也可以称之为弧(Arc)，我们用有序偶<Vi，Vj>表示。

我们将 Vi 称为弧<Vi，Vj>的弧尾(tail)或初始点(Initial node)，将 Vj 称为弧<Vi，Vj>的弧头(head)或终端点(Terminal node)。

<Vi，Vj>代表 Vi、Vj 之间具有一条有向边，方向为 Vi 指向 Vj 。

注意：对于无向边（Vi，Vj），我们可以随意改变其前后的顺序，及（Vj，Vi）与（Vi，Vj）表示的是同一条无向边；而对于有向边<Vi，Vj>，我们不能随意改变其前后的顺序，及<Vi，Vj>表示的是有向边Vi→Vj，而<Vj，Vi>表示的则是有向边Vj→Vi。

无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。
有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs），图1.1就是一张有向图。

关于无向图与有向图，大家可以联想一下你家到超市的道路与高速公路：

从你家到超市假如只有一条路通道A，你从Home出发到达超市所要经过的道路和你从超市回Home所要经过的道路是同一条道路通道A。所以此时通道A是无向的道路。

我们假设在城市A与城市B之间有建设高速公路X、Y。当我们从城市A出发前往城市B的时候，我们只能选择高速公路X出发；当我们从城市B返回城市A的时候，我们也只能选择高速公路Y出发。此时高速公路X与高速公路Y就是两个有向的道路。类似的场景还有坐地铁，坐火车等等。