topological sort template

2.怎么得出拓扑序？

有两种方法，分别基于BFS和DFS，时间复杂度都是O(|V| + |E|)。
Topological Sort: DFS and BFS
DFS:
据说这是神书《算法导论》中提到的算法：用深度搜索来遍历整个图，采用一个数组来保存每个顶点完成的时间，这样这个数组就存放了按先后顺序访问完成的顶点了。然后我们按照顶点访问的完成时间从大到小排序，得到的就是一个拓扑序了，具体证明如下（来自其他博客）：&……%¥¥……&&

Coding:

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
class Solution {
public:
    vector<int> topologicalSort(int n, vector<pair<int, int> >& edges) {
        vector<int> res;
        stack<int> s;
        int * isVisited = new int[n];
        for (int i = 0; i < n; i++) {
            isVisited[i] = 0;
        } 
        for (int i = 0; i < n; i++) {
            if (!isVisited[i]) dfs(edges, s, isVisited, i);
        }
        while (!s.empty()) {
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
    void dfs(vector<pair<int, int> >& edges, stack<int> & s, int * isVisited, int u) {
        isVisited[u] = 1;
        for (int i = 0; i < edges.size(); i++) {
            if (edges[i].first == u && !isVisited[edges[i].second]) {
                dfs(edges, s, isVisited, edges[i].second);
            }
        }
        s.push(u);
    } 
};

BFS:

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
class Solution {
public:
    vector<int> topologicalSort(int n, vector<pair<int, int> >& edges) {
        vector<int> res;
        vector<vector<int> > newedges(n, vector<int>());
        queue<int> q;
        vector<int> in_degree(n, 0);
        for (int i = 0; i < edges.size(); i++) {
            in_degree[edges[i].second]++;
            newedges[edges[i].first].push_back(edges[i].second);
        }
        for (int i = 0; i < n; i++) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int front = q.front();
            q.pop();
            res.push_back(front);
            for (int i = 0; i < newedges[front].size(); i++) {
                in_degree[newedges[front][i]]--;
                if (in_degree[newedges[front][i]] == 0) q.push(newedges[front][i]);
            }
        }
        return res;
    }
};

4.抛开这道题目——有环情况的判断

可以利用上面的dfs方法，比如isVisited这个数组，我们可以多增一种情况，比如0为未访问，1为已访问，-1为正在访问，当dfs搜索时遇到了一条边终止顶点对应的isVisited元素为-1时，就说明图中有环了（为-1说明我们是从这个顶点开始dfs的，现在又遇到了这个顶点…）。

另外一种判断图是否有环的方法，借助bfs（dfs也可，但既然用了dfs，直接用上面的方法好了），假如“生成拓扑序”后，还有顶点不在这个“拓扑序”里面，则图就有环了（加双引号是因为不能真正称作“拓扑序”啊）。