• 概述

    • Kruskal算法

    Kruskal算法核心在于对边按照权值排序，然后将不联通的边联通起来。需要借助并查集动态判断图是否联通。

    • 找到最小生成树里的关键边和伪关键边

    给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

    请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

    请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree
    分析：
    判断关键边的标准为去掉该边后图不联通，或者去掉改变后最小生成树的权值和增加。判断图不联通可以通过并查集计数联通分量实现。
    判断伪关键边的标准为优先添加此边，若最小生成树的权值和不变，则为伪关键边。判断之前需要排除它不是关键边。
    参考解答：

    1. class UnionFind:
    2.     def __init__(self, n) -> None:
    3.         self.f = list(range(n))
    4.         self.count = n
    5.     def find(self, p):
    6.         if self.f[p] != p:
    7.             self.f[p] = self.find(self.f[p])
    8.         return self.f[p]
    9.     def union(self, p, q):
    10.         pRoot = self.find(p)
    11.         qRoot = self.find(q)
    12.         if pRoot == qRoot:
    13.             return False
    14.         self.f[pRoot] = qRoot
    15.         self.count -= 1
    16.         return True
    17.     def getCount(self):
    18.         return self.count
    19. class Solution:
    20.     def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
    21.         m = len(edges)
    22.         for i, edge in enumerate(edges):
    23.             edge.append(i)
    24.         edges.sort(key=lambda x:x[2])
    25.         uf_std = UnionFind(n)
    26.         cost = 0
    27.         for edge in edges:
    28.             if uf_std.union(edge[0], edge[1]):
    29.                 cost += edge[2]
    30.         ret = [list(), list()]
    31.         for i in range(m):
    32.             uf = UnionFind(n)
    33.             v = 0
    34.             for j in range(m):
    35.                 if i != j and uf.union(edges[j][0], edges[j][1]):
    36.                     v += edges[j][2]
    37.             if uf.getCount() != 1 or (uf.getCount() == 1 and v > cost):
    38.                 ret[0].append(edges[i][3])
    39.                 continue
    40.             uf = UnionFind(n)
    41.             uf.union(edges[i][0], edges[i][1])
    42.             v = edges[i][2]
    43.             for j in range(m):
    44.                 if i != j and uf.union(edges[j][0], edges[j][1]):
    45.                     v += edges[j][2]
    46.             if v == cost:
    47.                 ret[1].append(edges[i][3])
    48.         return ret