最小生成树的扩展算法：探索变体和扩展应用，拓展你的算法知识

# 1. 最小生成树基础**

最小生成树 (MST) 是一种算法，用于在加权无向图中找到连接所有顶点的边集，使得总权重最小。MST 在计算机科学和网络优化等领域有着广泛的应用。

MST 的构建通常使用两种经典算法：Kruskal 算法和 Prim 算法。Kruskal 算法从所有边中选择权重最小的边，依次添加到 MST 中，直到所有顶点连接。Prim 算法从一个顶点开始，依次选择权重最小的边连接到 MST 中的顶点，直到所有顶点连接。

# 2. 最小生成树的变体

最小生成树（MST）算法在现实世界中有着广泛的应用，但有时需要根据特定问题进行调整。本章将介绍两种常见的 MST 变体：加权 MST 和有向 MST。

### 2.1 加权最小生成树

加权 MST 考虑了边权重，其目标是在满足生成树条件下，找到总权重最小的生成树。

#### 2.1.1 Kruskal 算法

Kruskal 算法是一种贪心算法，通过以下步骤构造加权 MST：

1. 将图中的所有边按权重从小到大排序。
2. 从权重最小的边开始，依次加入生成树，直到生成树包含所有顶点。
3. 如果加入某条边会形成环，则跳过该边。

**代码块：**

def kruskal_mst(graph):
    """
    Kruskal 算法求加权 MST

    参数：
        graph: 图，以邻接表形式表示

    返回：
        加权 MST 的边集合
    """
    # 初始化并查集
    uf = UnionFind(len(graph))

    # 边按权重排序
    edges = sorted(graph.edges(), key=lambda e: e.weight)

    # 逐条加入边
    mst_edges = []
    for edge in edges:
        if uf.find(edge.src) != uf.find(edge.dst):
            mst_edges.append(edge)
            uf.union(edge.src, edge.dst)

    return mst_edges

**逻辑分析：**

* `UnionFind` 类用于维护并查集，实现集合合并和查找操作。
* `graph.edges()` 返回图中所有边的迭代器。
* `sorted()` 函数按权重对边进行排序。
* 循环遍历排序后的边，如果加入该边不会形成环（即顶点属于不同的集合），则将其加入 MST。
* `uf.find()` 和 `uf.union()` 分别用于查找顶点的集合并合并集合。

#### 2.1.2 Prim 算法

Prim 算法也是一种贪心算法，其步骤如下：

1. 选择一个顶点作为起始点。
2. 从起始点出发，依次选择权重最小的边，将其加入生成树。
3. 如果加入某条边会形成环，则跳过该边。

**代码块：**

def prim_mst(graph, start):
    """
    Prim 算法求加权 MST

    参数：
        graph: 图，以邻接表形式表示
        start: 起始顶点

    返回：
        加权 MST 的边集合
    """
    # 初始化优先队列
    pq = PriorityQueue()

    # 将起始顶点加入优先队列
    pq.put(start, 0)

    # 初始化 MST
    mst_edges = []

    # 循环遍历优先队列
    while not pq.empty():
        # 取出权重最小的顶点
        vertex, weight = pq.get()

        # 加入 MST
        mst_edges.append((vertex, weight))

        # 遍历该顶点的相邻边
        for neighbor, edge_weight in graph.neighbors(vertex):
            # 如果相邻顶点不在 MST 中
            if neighbor not in mst_edges:
                # 将相邻边加入优先队列
                pq.put(neighbor, edge_weight)

    return mst_edges

**逻辑分析：**

* `PriorityQueue` 类用于维护优先队列，实现优先级插入和弹出操作。
* `graph.n