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.
http://www.lintcode.com/en/problem/topological-sorting/
Discussion
DFS + stack. 因为图可能不联通，所以不能从某一个node出发DFS，而应该从每一个没有被访问过的node出发。
Solution
/**
* 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*> result;
int n = graph.size();
if(n==0) return result;
stack<DirectedGraphNode*> nodestk;
unordered_map<DirectedGraphNode*, bool> isVisited;
for(int i=0; i<n; i++) {
if(isVisited.find(graph[i]) == isVisited.end()) {
dfs(graph[i], isVisited, nodestk);
}
}
while(nodestk.empty() == false) {
result.push_back(nodestk.top());
nodestk.pop();
}
return result;
}
void dfs(DirectedGraphNode* curNode,
unordered_map<DirectedGraphNode*, bool> &isVisited, stack<DirectedGraphNode*> &stk) {
//put node into the stack only after all its neighbors has been visited
isVisited[curNode] = true;
for(int i=0; i<curNode->neighbors.size(); i++) {
if(isVisited.find(curNode->neighbors[i]) == isVisited.end()) {
dfs(curNode->neighbors[i], isVisited, stk);
}
}
stk.push(curNode);
}
};
Iteration
void topSortHelper(DirectedGraphNode* node, unordered_set<DirectedGraphNode*> &is_visited,
stack<DirectedGraphNode*> &stk) {
stack<DirectedGraphNode*> mystk;
is_visited.emplace(node);
mystk.emplace(node);
while(!mystk.empty()) {
DirectedGraphNode *cur = mystk.top();
bool all = true;
for(auto const & v: cur->neighbors) {
if(is_visited.find(v) == is_visited.end()) {
mystk.emplace(v);
is_visited.emplace(v);
all = false;
break;//这里老是忘。。。
}
}
if(all) {
mystk.pop();
stk.emplace(cur);
}
}
}
Follow up
也可以通过计算indgree，BFS实现。
拓扑排序是假定图里面没有cycle的，关于如何判断图中是否存在cycle参考这篇文章。