堆在图算法中的魔法：最小生成树与迪杰斯特拉算法

# 1. 图算法概述**

图算法是一类用于解决图论问题的算法。图论是数学的一个分支，它研究由节点和边组成的结构，称为图。图算法在计算机科学中广泛应用，例如：网络规划、路径规划和数据挖掘。

图算法的基本概念包括：

* **图：**由节点和边组成的结构。节点表示实体，边表示实体之间的关系。
* **节点：**图中的基本元素，表示实体。
* **边：**连接两个节点的线段，表示实体之间的关系。
* **权重：**边上的值，表示边与之关联的成本或距离。

# 2. 最小生成树算法

最小生成树算法是一种贪心算法，用于在给定带权无向图中找到一个权值最小的生成树。生成树是指包含图中所有顶点的连通子图，且不包含任何环。

### 2.1 克鲁斯卡尔算法

#### 2.1.1 算法原理

克鲁斯卡尔算法通过以下步骤构造最小生成树：

1. 将图中的所有边按照权值从小到大排序。
2. 从权值最小的边开始，依次考虑每条边。
3. 如果添加该边不会形成环，则将该边加入生成树。
4. 重复步骤 3，直到生成树包含图中所有顶点。

#### 2.1.2 代码实现

def kruskal(graph):
    # 初始化并查集
    parent = [i for i in range(len(graph))]
    rank = [0 for i in range(len(graph))]

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

    # 构造最小生成树
    mst = []
    for edge in edges:
        if find(parent, edge.u) != find(parent, edge.v):
            union(parent, rank, edge.u, edge.v)
            mst.append(edge)

    return mst

# 并查集：查找根节点
def find(parent, node):
    if parent[node] == node:
        return node
    return find(parent, parent[node])

# 并查集：合并两个集合
def union(parent, rank, u, v):
    u_root = find(parent, u)
    v_root = find(parent, v)
    if u_root == v_root:
        return

    if rank[u_root] < rank[v_root]:
        parent[u_root] = v_root
    else:
        parent[v_root] = u_root
        if rank[u_root] == rank[v_root]:
            rank[u_root] += 1

**逻辑分析：**

* `find()` 函数使用递归查找节点的根节点。
* `union()` 函数使用并查集合并两个集合，并更新秩。
* `kruskal()` 函数按权值排序边，并使用并查集贪心地构造最小生成树。

### 2.2 普里姆算法

#### 2.2.1 算法原理

普里姆算法通过以下步骤构造最小生成树：

1. 选择一个顶点作为起始点。
2. 从起始点出发，找到权值最小的边连接到未包含在生成树中的顶点。
3. 将该边加入生成树。
4. 重复步骤 2 和 3，直到生成树包含图中所有顶点。

#### 2.2.2 代码实现

def prim(graph, start):
    # 初始化
    visited = [False for i in range(len(graph))]
    visited[start] = True
    mst = []

    # 循环添加边
    while len(mst) < len(graph) - 1:
        # 找到权值最小的边
        min_edge = None
        for u in range(len(graph)):
            if visited[u]: