掌握图论算法理论实现及应用核心

import heapq
def dijkstra(graph, start):
    """
    使用优先队列（最小堆）实现Dijkstra算法
    :param graph: 邻接表形式的图，例如 {1: {2: 1, 3: 4}, 2: {3: 2}, 3: {}}
    :param start: 起始节点
    :return: 最短距离字典
    """
    # 初始化距离，所有节点设为无穷大
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # 优先队列，存储 (距离, 节点)
    pq = [(0, start)]
    while pq:
        current_dist, current_node = heapq.heappop(pq)
        # 如果当前距离大于记录的最短距离，跳过
        if current_dist > distances[current_node]:
            continue
        # 遍历邻居
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            # 松弛操作
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances
示例用法
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1},
    'D': {}
}
print(dijkstra(graph, 'A'))
输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

#include <vector>
#include <numeric>
class UnionFind {
public:
    std::vector<int> parent;
    UnionFind(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 简单合并，未使用按秩合并
        }
    }
};