Chapter 5 Graph

    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    # 初始化队列（入度为0的顶点）
    queue = deque([u for u in in_degree if in_degree[u] == 0])
    result = []

    # BFS处理
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # 环检测
    return result if len(result) == len(graph) else "图中有环，无法生成拓扑序列"
```

**DFS算法（基于后序遍历反转）**

```python
def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(u):
        if u in visited:
            return
        visited.add(u)
        for v in graph[u]:
            dfs(v)
        stack.append(u)  # 后序入栈

    for u in graph:
        if u not in visited:
            dfs(u)

    return stack[::-1]  # 反转后序得到拓扑序列
```

---

**4. 应用场景**

| 场景                | 示例                                                                 |
|---------------------|----------------------------------------------------------------------|
| **任务调度**        | 编译顺序（如C++头文件依赖、Makefile规则）                           |
| **课程选修**        | 先修课程必须排在后续课程之前（如数据结构→算法）                     |
| **工作流管理**      | 生产流程中工序的先后依赖（如组装→测试→包装）                        |
| **依赖解析**        | 软件包安装的依赖关系（如npm/yarn包管理）                            |

---

**5. 经典示例**

课程依赖关系：

- 顶点：`C1`（高数）, `C2`（线代）, `C3`（数据结构）, `C4`（算法）
- 边：`C1→C3`, `C2→C3`, `C3→C4`

**可能的拓扑序列**：

- `[C1, C2, C3, C4]`
- `[C2, C1, C3, C4]`
- `[C1, C2, C3, C4]`（多个合法解，因C1和C2无依赖）

---

**6. 特殊说明**

- **环的检测**：若算法返回的序列长度≠顶点总数，说明图中存在环。
- **动态图处理**：某些场景需支持动态添加顶点/边并维护拓扑序列（如实时任务调度系统）。
- **加权扩展**：若需要处理带权依赖（如最短时间路径），需结合**AOE网络**和关键路径算法。