本文共 2406 字，大约阅读时间需要 8 分钟。
BFS:
1 /** 2 * Definition for Directed graph. 3 * struct DirectedGraphNode { 4 * int label; 5 * vector neighbors; 6 * DirectedGraphNode(int x) : label(x) {}; 7 * }; 8 */ 9 class Solution {10 public:11 /**12 * @param graph: A list of Directed graph node13 * @return: Any topological order for the given graph.14 */15 vector topSort(vector graph) {16 // write your code here17 vector topo;18 unordered_map degrees = compute_indegree(graph);19 queue zeros;20 for (auto itr = degrees.begin(); itr != degrees.end(); itr++)21 if ((*itr).second == 0)22 zeros.push((*itr).first);23 while (!zeros.empty()) {24 DirectedGraphNode* zero = zeros.front();25 zeros.pop();26 topo.push_back(zero);27 for (DirectedGraphNode* neigh : zero -> neighbors)28 if (--degrees[neigh] == 0)29 zeros.push(neigh);30 }31 return topo;32 }33 private:34 unordered_map compute_indegree(vector & graph) {35 unordered_map degrees;36 for (DirectedGraphNode* node : graph) {37 if (degrees.find(node) == degrees.end())38 degrees[node] = 0;39 for (DirectedGraphNode* neigh : node -> neighbors)40 degrees[neigh]++;41 }42 return degrees;43 }44 }; DFS:
1 /** 2 * Definition for Directed graph. 3 * struct DirectedGraphNode { 4 * int label; 5 * vector neighbors; 6 * DirectedGraphNode(int x) : label(x) {}; 7 * }; 8 */ 9 class Solution {10 public:11 /**12 * @param graph: A list of Directed graph node13 * @return: Any topological order for the given graph.14 */15 vector topSort(vector graph) {16 // write your code here17 vector topo;18 unordered_set visited;19 for (DirectedGraphNode* node : graph)20 if (visited.find(node) == visited.end())21 dfs(graph, node, visited, topo);22 reverse(topo.begin(), topo.end());23 return topo;24 }25 private:26 void dfs(vector & graph, DirectedGraphNode* node, 27 unordered_set & visited, 28 vector & topo) {29 visited.insert(node);30 for (DirectedGraphNode* neigh : node -> neighbors)31 if (visited.find(neigh) == visited.end())32 dfs(graph, neigh, visited, topo);33 topo.push_back(node);34 }35 };
转载地址：http://lyroa.baihongyu.com/