Topological Sorting

Posted on Edited on In Waline:

Today, I read an article about the ideas and applications of topological sorting, and I manually implemented it.

Data structure

Algorithms are built on concrete data structures. For this problem, let’s first look at how to abstract the problem background into concrete data structures.

We can abstract the dependency relationship between source files and source files into a directed graph. Each source file corresponds to a vertex in the graph, and the dependency relationship between source files is the edge between the vertices.

If a executes before b, that is, b depends on a, then between vertices a and b, build an edge from a to b. Moreover, this graph must not only be a directed graph, but also a Directed Acyclic Graph, that is, there cannot be a circular dependency like a- > b- > c- > a. Because once a ring appears in the graph, topological sorting cannot work. In fact, topological sorting itself is an algorithm based on Directed Acyclic Graph.

First, we define the data structure of the following figure

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 algorithm

The Kahn algorithm actually uses the idea of greedy algorithm, and the idea is very simple and easy to understand.

When defining a data structure, if s needs to be executed before t, then add an edge with s pointing to t. Therefore, if a vertex has a degree of 0, it means that no vertex must be executed before this vertex, then this vertex can be executed.

We first find a vertex with an incident degree of 0 from the graph, output it to the result sequence of topological sorting (the corresponding code is to print it), and delete this vertex from the graph (that is, the vertex can be removed from the graph). Decrease the incident of all reachable vertices by 1). We loop through the above process until all vertices are output. The final output sequence is a topological ordering that satisfies local dependencies.

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);
    }
}

This algorithm contains two key parts.

The first part is to construct the inverse adjacency table through the adjacency table. In the adjacency table, edge s- > t means that s executes before t, that is, t depends on s. In the inverse adjacency table, edge s- > t means that s depends on t, and s executes after t. Why this transformation? This is related to the implementation idea of our algorithm.

The second part is the core of this algorithm, that is, recursion processes each vertex. ** For vertex vertex, we first output all the vertices it can reach, that is, output all the vertices it depends on first, and then output itself **.