DFS

In this doc I will record some generic tricks and tips to implement Depth First Search (DFS) in programming, as well as some problems I hit when I was solving problems with DFS.

Topological Sort

Generic Idea

拓扑排序（Topological Sort）是一种用于有向无环图（DAG, Directed Acyclic Graph）的线性排序，使得对于图中的每一条有向边 (u, v)，顶点 u 在 v 之前出现在排序中。简而言之，拓扑排序就是对一个有向图进行排序，使得每个节点都在它所有前驱节点之后出现。

拓扑排序的输出结果是一个线性序列，可以用于解决很多实际问题，例如编译器的依赖关系分析、任务调度等。
这个结果不是唯一的，一个有向无环图可能有多个拓扑排序。

拓扑排序的具体实现步骤通常使用深度优先搜索（DFS）或基于入度的贪心算法（Kahn’s Algorithm）。以下是一个使用 DFS 实现拓扑排序的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Graph is a dictionary that represents the graph: from node to its neighbors, all integers
typealias Graph = [Int: [Int]]
func topologicalSort(_ graph: Graph) -> [Int] {
    var visited = Array(repeating: Int, count: graph.count)
    var result = [Int]()
    func dfs(_ node: Int) {
        visited[node] = 1
        for neighbor in graph[node] {
            // If the neighbor is not visited, visit it
            if visited[neighbor] == 0 {
                dfs(neighbor)
            }
        }
        result.append(node)
    }

    for node in graph.keys {
        if visited[node] == 0 {
            dfs(node)
        }
    }

    // The result is in reversed order because we append the node to the result after visiting all its neighbors
    return result.reversed()
}

// example
let graph = Graph(0: [1, 2], 1: [3], 2: [3], 3: [])
let result = topologicalSort(graph)
print(result) // [0, 2, 1, 3]

How to Detect Cycle

在拓扑排序中，如果图中存在环，那么这个图就不可能有拓扑排序。因此，我们需要在 DFS 过程中检测环的存在。

在 DFS 过程中，如果我们遇到了一个已经被访问过的节点，那么这个节点就是环的起点。我们可以通过一个数组 visited 来记录节点的访问状态，如果一个节点已经被访问过，那么它的状态就是 1。如果在 DFS 过程中遇到了一个已经被访问过的节点，那么就说明存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Graph is a dictionary that represents the graph: from node to its neighbors, all integers
typealias Graph = [Int: [Int]]
func topologicalSort(_ graph: Graph) -> [Int] {
    // 0: not visited; 1: in one path, if appear again, cycle; 2: visited and this is a good one without cycle
    var visited = Array(repeating: Int, count: graph.count)
    var result = [Int]()

    func dfs(_ node: Int) -> Bool {
        if visited[node] == 1 { return false }
        if visited[node] == 2 { return true }

        visited[node] = 1
        for neighbor in graph[node] { if !dfs(neighbor) { return false } }
        visited[node] = 2

        result.append(node)
        return true
    }

    for node in graph.keys { if !dfs(node) { return [] } }
    return result.reversed()
}
        
// example
let graph = Graph(0: [1, 2], 1: [3], 2: [3], 3: [0])
let result = topologicalSort(graph)
print(result) // []