Topological Sorting · 數據結構與算法/leetcode/lintcode題解

# Topological Sorting ### Source - lintcode: [(127) Topological Sorting](http://www.lintcode.com/en/problem/topological-sorting/) - [Topological Sorting - GeeksforGeeks](http://www.geeksforgeeks.org/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. ~~~ ExampleFor graph as follow: ![Topological Sorting](https://box.kancloud.cn/2015-10-24_562b1f6911978.jpeg) ~~~ The topological order can be: [0, 1, 2, 3, 4, 5] [0, 2, 3, 1, 5, 4] ... Note You can assume that there is at least one topological order in the graph. Challenge Can you do it in both BFS and DFS? ~~~ ### 題解1 - [DFS](# "Depth-First Search, 深度優先搜索") and [BFS](# "Breadth-First Search, 廣度優先搜索") 圖搜索相關的問題較為常見的解法是用 [DFS](# "Depth-First Search, 深度優先搜索")，這里結合 [BFS](# "Breadth-First Search, 廣度優先搜索") 進行求解，分為三步走： 1. 統計各定點的入度——只需統計節點在鄰接列表中出現的次數即可知。 1. 遍歷圖中各節點，找到入度為0的節點。 1. 對入度為0的節點進行遞歸 [DFS](# "Depth-First Search, 深度優先搜索")，將節點加入到最終返回結果中。 ### C++ ~~~ /** * 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) { vector<DirectedGraphNode*> result; if (graph.size() == 0) return result; map<DirectedGraphNode*, int> indegree; // get indegree of all DirectedGraphNode indeg(graph, indegree); // dfs recursively for (int i = 0; i < graph.size(); ++i) { if (indegree[graph[i]] == 0) { dfs(indegree, graph[i], result); } } return result; } private: /** get indegree of all DirectedGraphNode * */ void indeg(vector<DirectedGraphNode*> &graph, map<DirectedGraphNode*, int> &indegree) { for (int i = 0; i < graph.size(); ++i) { for (int j = 0; j < graph[i]->neighbors.size(); j++) { if (indegree.find(graph[i]->neighbors[j]) == indegree.end()) { indegree[graph[i]->neighbors[j]] = 1; } else { indegree[graph[i]->neighbors[j]] += 1; } } } } void dfs(map<DirectedGraphNode*, int> &indegree, DirectedGraphNode *i, vector<DirectedGraphNode*> &ret) { ret.push_back(i); indegree[i]--; for (int j = 0; j < i->neighbors.size(); ++j) { indegree[i->neighbors[j]]--; if (indegree[i->neighbors[j]] == 0) { dfs(indegree, i->neighbors[j], ret); } } } }; ~~~ ### 源碼分析 C++中使用 unordered_map 可獲得更高的性能，私有方法中使用引用傳值。 ### 復雜度分析以 V 表示頂點數，E 表示有向圖中邊的條數。首先獲得節點的入度數，時間復雜度為 O(V+E)O(V+E)O(V+E), 使用了哈希表存儲，空間復雜度為 O(V)O(V)O(V). 遍歷圖求得入度為0的節點，時間復雜度為 O(V)O(V)O(V). 僅在入度為0時調用 [DFS](# "Depth-First Search, 深度優先搜索")，故時間復雜度為 O(V+E)O(V+E)O(V+E). 需要注意的是這里的 [DFS](# "Depth-First Search, 深度優先搜索") 不是純 [DFS](# "Depth-First Search, 深度優先搜索")，使用了 [BFS](# "Breadth-First Search, 廣度優先搜索") 的思想進行了優化，否則一個節點將被遍歷多次，時間復雜度可能惡化為指數級別。綜上，時間復雜度近似為 O(V+E)O(V+E)O(V+E), 空間復雜度為 O(V)O(V)O(V). ### 題解2 - [BFS](# "Breadth-First Search, 廣度優先搜索") 拓撲排序除了可用 [DFS](# "Depth-First Search, 深度優先搜索") 求解外，也可使用 [BFS](# "Breadth-First Search, 廣度優先搜索"), 具體方法為： 1. 獲得圖中各節點的入度。 1. [BFS](# "Breadth-First Search, 廣度優先搜索") 首先遍歷求得入度數為0的節點，入隊，便于下一次 [BFS](# "Breadth-First Search, 廣度優先搜索")。 1. 隊列不為空時，彈出隊頂元素并對其鄰接節點進行 [BFS](# "Breadth-First Search, 廣度優先搜索")，將入度為0的節點加入到最終結果和隊列中，重復此過程直至隊列為空。 ### C++ ~~~ /** * 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) { vector<DirectedGraphNode*> result; if (graph.size() == 0) return result; map<DirectedGraphNode*, int> indegree; // get indegree of all DirectedGraphNode indeg(graph, indegree); queue<DirectedGraphNode*> q; // bfs bfs(graph, indegree, q, result); return result; } private: /** get indegree of all DirectedGraphNode * */ void indeg(vector<DirectedGraphNode*> &graph, map<DirectedGraphNode*, int> &indegree) { for (int i = 0; i < graph.size(); ++i) { for (int j = 0; j < graph[i]->neighbors.size(); j++) { if (indegree.find(graph[i]->neighbors[j]) == indegree.end()) { indegree[graph[i]->neighbors[j]] = 1; } else { indegree[graph[i]->neighbors[j]] += 1; } } } } void bfs(vector<DirectedGraphNode*> &graph, map<DirectedGraphNode*, int> &indegree, queue<DirectedGraphNode *> &q, vector<DirectedGraphNode*> &ret) { for (int i = 0; i < graph.size(); ++i) { if (indegree[graph[i]] == 0) { ret.push_back(graph[i]); q.push(graph[i]); } } while (!q.empty()) { DirectedGraphNode *cur = q.front(); q.pop(); for(int j = 0; j < cur->neighbors.size(); ++j) { indegree[cur->neighbors[j]]--; if (indegree[cur->neighbors[j]] == 0) { ret.push_back(cur->neighbors[j]); q.push(cur->neighbors[j]); } } } } }; ~~~ ### 源碼分析 C++中在判斷入度是否為0時將對 map 產生副作用，在求入度數時只有入度數大于等于1才會出現在 map 中，故不在 map 中時直接調用 indegree 方法將產生新的鍵值對，初始值為0，恰好滿足此題需求。 ### 復雜度分析同題解1 的分析，時間復雜度為 O(V+E)O(V+E)O(V+E), 空間復雜度為 O(V)O(V)O(V). ### Reference - [Topological Sorting 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/topological-sorting/)