拓扑排序：如何确定代码源文件的编译依赖关系？

我们知道，一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那在编译的时候，编译器需要先编译 B.cpp，才能编译 A.cpp。

编译器通过分析源文件或者程序员事先写好的编译配置文件（比如 Makefile 文件），来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？ 这个问题的解决思路与“图”这种数据结构的一个经典算法“拓扑排序算法”有关。那什么是拓扑排序呢？

什么是拓扑排序

拓扑排序是一种对有向无环图（DAG）进行线性排序的方法，使得对于图中的每一条有向边 (u, v)，顶点 u 总是在顶点 v 之前出现。 拓扑排序常用于解决依赖关系问题，比如任务调度、课程安排等。

拓扑排序的特点

1. 存在性：只有在图是无环的情况下，才能进行拓扑排序。
2. 不唯一性：一个图可能有多个有效的拓扑排序结果。

应用场景

• 任务调度：根据任务依赖关系确定执行顺序。
• 编译器：确定编译模块的顺序。
• 项目管理：确定项目活动的顺序。

常用算法

Kahn 算法

1. 初始化：创建一个入度为 0 的顶点集合 S。
2. 处理：从 S 中取出一个顶点 v 并输出。
3. 更新：对于 v 的每一个邻接顶点 w，减少 w 的入度。如果 w 的入度变为 0，则将 w 加入 S。
4. 重复：重复步骤 2 和 3，直到 S 为空。
5. 检查：如果输出的顶点数等于图中的顶点数，则图是一个有向无环图，否则图中存在环。

基于 DFS 的算法

1. 初始化：创建一个栈 L 用于存储排序结果，创建一个布尔数组 visited 用于记录每个顶点是否已被访问。
2. 递归：对于每个未访问的顶点 v，调用递归函数 DFS(v)。
3. 递归函数：
   • 标记 v 为已访问。
   • 对于 v 的每一个邻接顶点 w，如果 w 未被访问，则递归调用 DFS(w)。
   • 访问完 v 的所有邻接顶点后，将 v 推入栈 L。
4. 输出：从栈 L 中依次弹出顶点，即为拓扑排序的结果。

示例

假设有一个有向图，顶点集 V = {A, B, C, D, E}，边集 E = {(A, B), (A, C), (B, D), (C, D), (D, E)}。

1. Kahn 算法：

   • 初始化：S = {A}
   • 处理 A：输出 A，更新 B 和 C 的入度，S = {B, C}
   • 处理 B：输出 B，更新 D 的入度，S = {C}
   • 处理 C：输出 C，更新 D 的入度，S = {D}
   • 处理 D：输出 D，更新 E 的入度，S = {E}
   • 处理 E：输出 E，S = {}
   • 结果：A, B, C, D, E

2. 基于 DFS 的算法：

   • 初始化：L = []，visited = [false, false, false, false, false]
   • 递归调用 DFS(A)
     • 访问 A，递归调用 DFS(B)
       • 访问 B，递归调用 DFS(D)
         • 访问 D，递归调用 DFS(E)
           • 访问 E，将 E 推入 L
         • 将 D 推入 L
       • 将 B 推入 L
     • 递归调用 DFS(C)
       • 访问 C，递归调用 DFS(D)（D 已访问，跳过）
       • 将 C 推入 L
     • 将 A 推入 L
   • 结果：A, C, B, D, E

Kahn 算法实现

import Foundation

func topologicalSort(vertices: Int, edges: [(Int, Int)]) -> [Int]? {
    
    var graph = Array(repeating: [Int](), count: vertices)
    var inDegree = Array(repeating: 0, count: vertices)

    // 构建图和计算入度
    for edge in edges {
        let (u, v) = edge
        graph[u].append(v)
        inDegree[v] += 1
    }

    
    var queue = [Int]()
    for i in 0..[i] == 0 {
            queue.append(i)
        }
    }

    var result = [Int]()

    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)

        
        for neighbor in graph[node] {
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0 {
                queue.append(neighbor)
            }
        }
    }

    
    if result.count == vertices {
        return result
    } else {
        return nil 
    }
}


let vertices = 6
let edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
if let sortedOrder = topologicalSort(vertices: vertices, edges: edges) {
    print("拓扑排序结果: (sortedOrder)")
} else {
    print("图中存在环，无法进行拓扑排序。")
}

基于 DFS 的算法

import Foundation


struct Node {
    let id: Int                
    var neighbors: [Int] = []  
}


class Graph {
    var nodes: [Node] = []     

    
    init(_ n: Int) {
        for i in 0..<n {
            nodes.append(Node(id: i)) 
        }
    }

    
    func addEdge(_ from: Int, _ to: Int) {
        nodes[from].neighbors.append(to) 
    }

    
    func topologicalSort() -> [Int]? {
        var visited = Array(repeating: false, count: nodes.count) 
        var stack: [Int] = [] 
        var hasCycle = false 

        
        func dfs(_ node: Int) {
            visited[node] = true 
            for neighbor in nodes[node].neighbors { 
                if !visited[neighbor] { 
                    dfs(neighbor) 
                } else if !stack.contains(neighbor) { 
                    
                    hasCycle = true
                    return
                }
            }
            stack.insert(node, at: 0) 
        }

        
        for i in 0..<nodes.count {
            if !visited[i] { 
                dfs(i) 
            }
        }

        
        if hasCycle {
            return nil 
        }

        return stack 
    }
}


let graph = Graph(6) 
graph.addEdge(5, 2) 
graph.addEdge(5, 0) 
graph.addEdge(4, 0) 
graph.addEdge(4, 1) 
graph.addEdge(2, 3) 
graph.addEdge(3, 1) 


if let result = graph.topologicalSort() {
    print("拓扑排序结果: (result)") 
} else {
    print("图中存在环，无法进行拓扑排序") 
}

解释

1. 图的定义：

   • Node 结构体表示图中的节点，包含节点的 ID 和其邻接节点列表。
   • Graph 类包含节点列表，并提供添加边的方法 addEdge。

2. 拓扑排序方法：

   • topologicalSort 方法初始化一个 visited 数组来记录每个节点是否已被访问，一个 stack 来存储排序结果，以及一个 hasCycle 标志来检测环。
   • dfs 是一个递归函数，用于深度优先遍历图。每次访问一个节点时，标记为已访问，并递归访问其所有邻接节点。如果发现某个邻接节点已经被访问但还没有入栈，说明存在环。
   • 遍历所有节点，调用 dfs 方法。最后，如果图中不存在环，返回 stack 中的节点顺序；否则返回 nil。

3. 示例：

   • 创建一个包含 6 个节点的图，并添加一些边。
   • 调用 topologicalSort 方法获取拓扑排序结果，并打印结果。

为什么在基于 DFS 的算法中如果邻居已经被访问过但还没有入栈，则说明存在环？

当我们在 DFS 过程中遇到一个已经被访问过的节点，但该节点尚未入栈时，这意味着存在一个环。以下是对这一判断条件的详细解释：

节点状态

在 DFS 过程中，每个节点可以处于以下三种状态之一：

1. 未访问：节点尚未被访问。
2. 正在访问：节点已经被访问，但其所有邻接节点尚未完全处理完毕。
3. 已访问：节点及其所有邻接节点已经完全处理完毕，并且该节点已经入栈。

判断条件

在 DFS 过程中，当我们访问一个节点 node 时，会递归地访问其所有邻接节点 neighbor。对于每个邻接节点 neighbor，有以下几种情况：

1. 未访问：如果 neighbor 未被访问过，则递归调用 dfs(neighbor)。
2. 正在访问：如果 neighbor 已经被访问过但尚未入栈，说明 neighbor 仍在当前的递归路径中。此时，从 node 到 neighbor 形成了一条回路，即存在环。
3. 已访问：如果 neighbor 已经被访问过并且已经入栈，说明 neighbor 已经处理完毕，不会形成环。

代码解释

在代码中，我们使用 visited 数组来记录节点是否已被访问，使用 stack 来记录已经处理完毕的节点。具体判断条件如下：

func dfs(_ node: Int) {
    visited[node] = true
    for neighbor in nodes[node].neighbors {
        if !visited[neighbor] {
            dfs(neighbor)
        } else if !stack.contains(neighbor) {
            
            hasCycle = true
            return
        }
    }
    stack.insert(node, at: 0)
}

• if !visited[neighbor]：如果邻接节点 neighbor 未被访问过，则递归调用 dfs(neighbor)。
• else if !stack.contains(neighbor)：如果邻接节点 neighbor 已经被访问过但尚未入栈，说明 neighbor 仍在当前的递归路径中，形成了一个环。此时，设置 hasCycle = true 并返回。

例子

考虑以下图的邻接表表示：

0 -> 1
1 -> 2
2 -> 3
3 -> 1

1. 从节点 0 开始 DFS：
   • 访问 0，标记 0 为已访问。
   • 访问 1，标记 1 为已访问。
   • 访问 2，标记 2 为已访问。
   • 访问 3，标记 3 为已访问。
   • 当访问 3 的邻接节点 1 时，发现 1 已经被访问过但尚未入栈，说明存在环。

我们可以看到，如果在 DFS 过程中遇到一个已经被访问过但尚未入栈的节点，说明存在一个环。这是因为该节点仍在当前的递归路径中，形成了一个回路。这种判断条件是基于节点状态的合理性和递归路径的特性。