图论基础 (Graph Theory)

图 (Graph) 是一种非线性数据结构，由 顶点 (Vertex/Node) 和 边 (Edge) 组成。

图的表示

1. 邻接矩阵 (Adjacency Matrix)

使用二维数组 matrix[i][j] 表示从 \(i\) 到 \(j\) 是否相连（或权重）。

• 优点: \(O(1)\) 判断两点是否相连。
• 缺点: 空间复杂度 \(O(V^2)\)，稀疏图浪费空间。

2. 邻接表 (Adjacency List)

使用字典或数组列表，graph[i] 存储所有与 \(i\) 相连的节点。

• 优点: 节省空间 \(O(V+E)\)。
• 缺点: 查找两点是否相连需要遍历链表。

# 邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

拓扑排序 (Topological Sort)

用于解决依赖关系问题（如课程表、任务调度）。仅适用于 有向无环图 (DAG)。

算法流程 (Kahn 算法)

1. 统计所有节点的入度 (In-degree)。
2. 将入度为 0 的节点放入队列。
3. 每次从队列取出一个节点，将其指向的邻居节点的入度减 1。
4. 如果邻居入度变为 0，加入队列。
5. 如果最终输出的节点数少于总节点数，说明有环。

from collections import deque

def topological_sort(num_courses, prerequisites):
    # 建图和入度表
    graph = {i: [] for i in range(num_courses)}
    in_degree = {i: 0 for i in range(num_courses)}

    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    # 入度为 0 入队
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    topo_order = []

    while queue:
        node = queue.popleft()
        topo_order.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return topo_order if len(topo_order) == num_courses else []

# 课程 1 依赖 0，课程 2 依赖 0，课程 3 依赖 1 和 2
# [1, 0] 表示修 1 之前要修 0
deps = [[1, 0], [2, 0], [3, 1], [3, 2]]
print(topological_sort(4, deps))
# 可能结果: [0, 1, 2, 3]

最短路径算法

Dijkstra 算法

用于计算从一个起点到其他所有节点的最短路径。 适用: 边权非负。 核心: BFS + 优先队列 (Min-Heap)。

import heapq

def dijkstra(graph, start):
    # graph 是 {node: [(neighbor, weight), ...]}
    pq = [(0, start)] # (距离, 节点)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    while pq:
        d, node = heapq.heappop(pq)

        if d > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

本章小结

图论非常庞大，还包括：

• 最小生成树 (MST): Prim, Kruskal 算法。
• 并查集 (Union-Find): 处理连通性问题神器。
• Bellman-Ford / Floyd: 处理带负权边或多源最短路。

掌握 BFS/DFS (遍历)、拓扑排序 (依赖) 和 Dijkstra (最短路) 是入门图论的基础。

---

算法基础篇完结！建议前往 LeetCode 进行实战练习。