图论基础：Kruskal算法与拓扑排序解析

"Kruskal算法是图论中的一个经典算法，用于解决最小生成树问题。该算法遵循贪心策略，即在每一步选择当前未加入森林的边中权值最小的一条，并检查这条边是否会与已有的边形成环。如果不会形成环，这条边就会被添加到森林中。Kruskal算法从n个顶点的集合开始，逐步构建最小生成树，直到所有的顶点都被连接起来。 图论是研究点和边之间关系的数学分支。在图论中，一个图G由顶点集V和边集E组成，记为G=(V,E)。图可以是有向的或无向的，有向图中的边具有方向，而无向图的边没有方向。顶点的度是指与该顶点相连的边的数量。在有向图中，分为入度（进入该顶点的边数）和出度（从该顶点出发的边数）。简单图是没有自环（一个顶点到自身的边）和重边（两个顶点间有多于一条边）的图。完全图是每个顶点都与其他所有顶点相连的图。平面图是指可以在平面上绘制，使得边不相交的图。二分图则是可以将顶点分成两个集合，使得每条边连接不同集合内的顶点的图。 图的存储结构通常有两种主要方式：邻接矩阵和邻接表。邻接矩阵是一个二维数组，用于表示图中每对顶点之间的连接关系，矩阵中的元素表示对应顶点之间边的权值。邻接表则是为每个顶点维护一个链表，链表中的节点表示与该顶点相连的所有其他顶点。 拓扑排序是针对有向无环图(DAG)的一种排序方法，它能够将DAG的顶点排列成一个线性序列，使得对于图中的每条有向边(u, v)，u总是在序列中出现在v之前。在拓扑排序过程中，首先找到所有入度为0的顶点，然后将它们加入序列，并更新其他顶点的入度。这个过程不断重复，直到所有顶点都被处理。如果最后能够将所有顶点都加入序列，那么图是有向无环图，拓扑排序成功；反之，如果存在环，则无法进行拓扑排序。 欧拉道路和欧拉回路是图论中的另一个重要概念。欧拉回路是一条通过图中每条边恰好一次的路径，起点和终点相同。如果图中的所有顶点的度都是偶数，那么存在欧拉回路是一个必要条件，同时也是充分条件。对于有向图，欧拉道路的概念类似，但入度和出度的平衡条件有所不同。如果图中所有顶点的入度等于出度，且至少有一个顶点的入度为0，那么存在欧拉道路。 Kruskal算法的正确性在于其始终选择最小的边，且在添加边时避免了环的形成。为了快速判断是否形成环，可以使用并查集数据结构，它能高效地检测两个顶点是否属于同一个连通分量，从而避免添加会导致环的边。在算法执行过程中，每当遇到一条新边，就检查它的两个端点是否已经在同一连通分量中，如果是，则忽略此边，否则将这两个端点合并到同一连通分量中，并将边添加到最小生成树中。通过这种方式，Kruskal算法最终能找到图的最小生成树。"