debug了好久,因此写一下最终的解决方法,并且顺便梳理一下“拓扑序”这个东西。

 

1.什么是拓扑序?

对一个有向无环图进行拓扑排序,假如图中存在一条从顶点A到顶点B的路径,则拓扑序中顶点A出现在顶点B的前面。要注意的是,这是对有向无环图而言的,假如图是有环的,拓扑序就无从谈起了。在这道题目中,已经假定了图是一个无环图。因此不需要进行检查。

 

2.怎么得出拓扑序?

有两种方法,分别基于BFS和DFS,时间复杂度都是O(|V| + |E|)。以这道题作为例子分别说一下:

(1)BFS

这是我最先想到的方法。我们需要:一个数组,统计每个顶点的入度数;一个队列用于bfs。首先遍历一次所有的边,将每个顶点的入度数都求出来,而入度数为0的顶点说明没有其他顶点指向它。因此先把入度数为0的顶点放进队列中。

接着用一个循环每次从队头取出front,把它放进返回结果的列表中。然后遍历一遍所有的边,假如当前边对应的起始顶点为front,则将边对应的终结顶点的入度数减1(我们把front放进结果中,也视作把front从图中去掉了,那入度数自然要减1了)。如果一个顶点的入度数变为0,说明已经没有其他顶点指向它了,就可以把它放入队尾。一直到队列为空时,说明拓扑序已经得到了。

代码如下:

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

 

 

(2)DFS

据说这是神书《算法导论》中提到的算法:用深度搜索来遍历整个图,采用一个数组来保存每个顶点完成的时间,这样这个数组就存放了按先后顺序访问完成的顶点了。然后我们按照顶点访问的完成时间从大到小排序,得到的就是一个拓扑序了,具体证明如下(来自其他博客):

 

在这道题中,肯定不用真的开一个数组啊,代码如下:

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易理解一点)

 

3.针对这道题……

So sad,以上两种方法在这道题都TLE了,因为对于每个顶点,我们都需要遍历一次边的数组,要想节省时间,我们就要花费空间,使对于每个顶点,我们只需要考虑以它为起始点的边。

真正能AC的代码:

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,假如“生成拓扑序”后,还有顶点不在这个“拓扑序”里面,则图就有环了(加双引号是因为不能真正称作“拓扑序”啊)。

 

版权声明:本文为fengziwei原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:http://www.cnblogs.com/fengziwei/p/7875355.html