Topological Sorting

Topological Sorting

Description:

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.

Notice:

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

Example:

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
…

分析：

不难，但是却没有很快写出来。一开始想着BFS，用队列实现，编码遇到问题，转而用下面的方法。

思路：

用一个数组incomming保存每个节点的入度，当入度为0就把它加入到rs中，并把它的入度设为-1。重复这步骤，直到incomming中没有0为止（此时所有节点都已经遍历并且incomming中全是-1，或者有不为-1也不为0的值，表示这个节点有回路：自回路或者和其它节点组成回路）。

参考：

Code：

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
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
    
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
        vector<DirectedGraphNode*> rs;
        if (graph.empty()) return rs;
        
        vector<int> incomming(graph.size(), 0);
        
        for (int i = 0; i < graph.size(); i++) {
            for (int j = 0; j < graph[i]->neighbors.size(); j++) {
                incomming[graph[i]->neighbors[j]->label]++;
            }
        }
        
        int pos = containZero(incomming);
        while(pos != -1) {
            incomming[pos] = -1;
            rs.push_back(graph[pos]);
            
            for (int j = 0; j < graph[pos]->neighbors.size(); j++) {
                incomming[graph[pos]->neighbors[j]->label]--;
            }
            
            pos = containZero(incomming);
        }
        
        return rs;
    }
    
    int containZero(const vector<int> &incomming) {
        for (int i = 0; i < incomming.size(); i++) {
            if (incomming[i] == 0) return i;
        }
        
        return -1;
    }
};