拓扑排序

发表于 更新于 分类于 Waline：

今天看了一篇关于拓扑排序的思路和应用的文章，自己手动实现记录一下。

数据结构

算法是构建在具体的数据结构之上的。针对这个问题，我们先来看下，如何将问题背景抽象成具体的数据结构？

我们可以把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。

如果 a 先于 b 执行，也就是说 b 依赖于 a，那么就在顶点 a 和顶点 b 之间，构建一条从 a 指向 b 的边。而且，这个图不仅要是有向图，还要是一个有向无环图，也就是不能存在像 a->b->c->a 这样的循环依赖关系。因为图中一旦出现环，拓扑排序就无法工作了。实际上，拓扑排序本身就是基于有向无环图的一个算法。

首先我们定义下图的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
class Graph{
    constructor(v) {
        this.v = v;
        this.adj = [];
        for(let i = 0; i < v; i++) {
            this.adj[i] = [];
        }
    }

    addEdge(s, t) { // s->t
        this.adj[s].push(t);
    }
}

Kahn算法

Kahn 算法实际上用的是贪心算法思想，思路非常简单、好懂。

定义数据结构的时候，如果 s 需要先于 t 执行，那就添加一条 s 指向 t 的边。所以，如果某个顶点入度为 0， 也就表示，没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行了。

我们先从图中，找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减 1）。我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

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
32
33
34
35
36
37
38
39
class Graph{
    constructor(v) {
        this.v = v;
        this.adj = [];
        for(let i = 0; i < v; i++) {
            this.adj[i] = [];
        }
    }

    addEdge(s, t) {
        this.adj[s].push(t);
    }

    topoSortByKahn() {
        let inDegree = new Array(this.v).fill(0);
        for(let i = 0; i < this.adj.length; i++) {
            for(let j = 0; j < this.adj[i].length; j++) {
                inDegree[this.adj[i][j]]++;
            }
        }
        let queue = [];
        for(let i = 0; i < this.v; i++) {
            if (inDegree[i] === 0) {
                queue.push(i);
            }
        }
        while(queue.length > 0) {
            const i = queue.unshift();
            console.log(i);
            for(let j = 0; j < this.adj[i].length; j++) {
                let k = this.adj[i][j];
                inDegree[k]--;
                if (inDegree[k] === 0) {
                    queue.push(k);
                }
            }
        }
    }
}

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
topoSortByDFS() {
    let inverseAdj = new Array(this.v).fill([]);
    for(let i = 0; i < this.v; i++) {
        for(let j = 0; j < this.adj[i].length; j++) {
            inverseAdj[this.adj[i][j]].push(i);
        }
    }
    let visited = new Array(this.v).fill(false);
    for(let i = 0; i < this.v; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(i);
        }
    }
    const dfs = (vertex) => {
        for(let i = 0; i < inverseAdj[vertex].length; i++) {
            const w = inverseAdj[vertex][i];
            if (visited[w]) {
                continue;
            }
            visited[w] = true;
            dfs(w);
        }
        console.log(vertex);
    }
}

这个算法包含两个关键部分。

第一部分是通过邻接表构造逆邻接表。邻接表中，边 s->t 表示 s 先于 t 执行，也就是 t 要依赖 s。在逆邻接表中，边 s->t 表示 s 依赖于 t，s 后于 t 执行。为什么这么转化呢？这个跟我们这个算法的实现思想有关。

第二部分是这个算法的核心，也就是递归处理每个顶点。对于顶点 vertex 来说，我们先输出它可达的所有顶点，也就是说，先把它依赖的所有的顶点输出了，然后再输出自己。