Topological Sorting

题目：

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.

The first node in the order can be any node in the graph with no nodes direct to it. Find any topological order for the given graph.

这个假设必须有，否则需要额外加入判断语句。存在topo sort的充要条件是directed acyclic graph，图中不可以有环。

You can assume that there is at least one topological order in the graph.

实际上，topo sort是用来判断有向图是否有环的一个不错的算法，如果topo sort的结果的size和graph的size相同，则没有环，否则就有环。而对于无向图中是否有环，则可以用“dfs三色法”来进行判断，这个算法对有向图无向图都有效。具体实现参见题目course schedule。

http://www.cnblogs.com/TenosDoIt/p/3644225.html

分析：

这道题目很重要，bfs, dfs都应该会，需要二次巩固。

如果用bfs做
1. 遍历所有的点和边，确定每个点的degree
2. 把所有degree为0的点放入Q。注意，是所有的degree为0的点！！！！！！
3. bfs遍历，每次把neighbors里的所有点degree -= 1

需要注意算法复杂度是O(E + V)而不是O(E x V)，他的嵌套循环是对每个点做它自己的边，而不是对每个点做所有边，因此尽管嵌套了循环，也不能按照乘法来考虑。

解法bfs：

class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        if (graph.size() == 0) {
            return vector<DirectedGraphNode*>();
        }
        unordered_map<DirectedGraphNode*, int> hash;
        for (int i = 0; i < graph.size(); i++) {
            for (int j = 0; j < graph[i]->neighbors.size(); j++) {
                if (hash.find(graph[i]->neighbors[j]) == hash.end() ) {
                    hash[graph[i]->neighbors[j] ] = 1;
                } else {
                    hash[graph[i]->neighbors[j] ] += 1;
                }
            }
        }

        queue<DirectedGraphNode*> Q;
        for (int i = 0; i < graph.size(); i++) {
            if (hash[graph[i]] == 0) {
                Q.push(graph[i]);
            }
        }

        vector<DirectedGraphNode*> res;
        while(!Q.empty() ) {
            DirectedGraphNode* temp = Q.front();
            Q.pop();
            res.push_back(temp);
            for (int i = 0; i < temp->neighbors.size(); i++) {
                hash[temp->neighbors[i] ] -= 1;
                if (hash[temp->neighbors[i] ] == 0) {
                    Q.push(temp->neighbors[i]);
                }
            }
        }
        return res;
    }
};

解法dfs：

class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    void dfs(DirectedGraphNode* node, 
            map<DirectedGraphNode*, int> &degree, 
            vector<DirectedGraphNode*> &res) {
        res.push_back(node);
        degree[node] -= 1;
        for (int i = 0; i < node->neighbors.size(); i++) {
            degree[node->neighbors[i] ] -= 1;
            if (degree[node->neighbors[i] ] == 0) {
                dfs(node->neighbors[i], degree, res);
            }
        }
    } 

    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        map<DirectedGraphNode*, int> degree;
        for (int i = 0; i < graph.size(); i++) {
            for (int j = 0; j < graph[i]->neighbors.size(); j++) {
                if (degree.find(graph[i]->neighbors[j]) == degree.end() ) {
                    degree[graph[i]->neighbors[j] ] = 1;
                } else {
                    degree[graph[i]->neighbors[j] ] += 1;
                }
            }
        }

        vector<DirectedGraphNode*> res;
        for (int i = 0; i < graph.size(); i++) {
            if (degree[graph[i] ] == 0) {
                dfs(graph[i], degree, res);
            }
        }
        return res;
    }
};