带你读《图解算法小抄》二十五、图（7）

带你读《图解算法小抄》二十五、图（6）https://developer.aliyun.com/article/1347767?groupCode=tech_library

一个平面图及其最小生成树。每条边都带有其权重，这里的权重大致与其长度成比例。

该图显示了图中可能有多个最小生成树的情况。在图中，下面的两棵树是给定图的两种最小生成树。

2）参考资料

• 维基百科上的最小生成树
  
• 维基百科上的克鲁斯卡尔算法
  
• YouTube上的Tushar Roy的克鲁斯卡尔算法
  
• YouTube上的Michael Sambol的克鲁斯卡尔算法
  

8.拓扑排序

在计算机科学领域，有向图的拓扑排序（Topological Sort）是对其顶点的一种线性排序，使得对于每条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 之前。

例如，图中的顶点可以表示要执行的任务，而边表示一个任务必须在另一个任务之前执行的约束；在这种应用中，拓扑排序就是任务的有效顺序。

只有当图没有有向环时，即为有向无环图（DAG），才可能存在拓扑排序。任何DAG都至少有一个拓扑排序，而且已知的算法可以在线性时间内构造任何DAG的拓扑排序。

有向无环图

有向无环图的拓扑排序：每条边从排序中的较早顶点（左上）指向较后顶点（右下）。有向图是无环的当且仅当它有一个拓扑排序。

带你读《图解算法小抄》二十五、图（8）https://developer.aliyun.com/article/1347765?groupCode=tech_library