Topological Sorting

Question

  1. Given an directed graph, a topological order of the graph nodes is defined as follow:
  3. For each directed edge A -> B in graph, A must before B in the order list.
  4. The first node in the order can be any node in the graph with no nodes direct to it.
  5. Find any topological order for the given graph.

Example
For graph as follow:

Topological Sorting

  1. The topological order can be:
  3. [0, 1, 2, 3, 4, 5]
  4. [0, 2, 3, 1, 5, 4]
  5. ...
  6. Note
  7. You can assume that there is at least one topological order in the graph.
  9. Challenge
  10. Can you do it in both BFS and DFS?

题解1 - DFS and BFS

图搜索相关的问题较为常见的解法是用 DFS，这里结合 BFS 进行求解，分为三步走：

  1. 统计各定点的入度——只需统计节点在邻接列表中出现的次数即可知。
  2. 遍历图中各节点，找到入度为0的节点。
  3. 对入度为0的节点进行递归 DFS，将节点加入到最终返回结果中。

C++

  1. /**
  2.  * Definition for Directed graph.
  3.  * struct DirectedGraphNode {
  4.  *     int label;
  5.  *     vector<DirectedGraphNode *> neighbors;
  6.  *     DirectedGraphNode(int x) : label(x) {};
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     /**
  12.      * @param graph: A list of Directed graph node
  13.      * @return: Any topological order for the given graph.
  14.      */
  15.     vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
  16.         vector<DirectedGraphNode*> result;
  17.         if (graph.size() == 0) return result;
  19.         map<DirectedGraphNode*, int> indegree;
  20.         // get indegree of all DirectedGraphNode
  21.         indeg(graph, indegree);
  22.         // dfs recursively
  23.         for (int i = 0; i < graph.size(); ++i) {
  24.             if (indegree[graph[i]] == 0) {
  25.                 dfs(indegree, graph[i], result);
  26.             }
  27.         }
  29.         return result;
  30.     }
  32. private:
  33.     /** get indegree of all DirectedGraphNode
  34.      *
  35.      */
  36.     void indeg(vector<DirectedGraphNode*> &graph,
  37.                   map<DirectedGraphNode*, int> &indegree) {
  39.         for (int i = 0; i < graph.size(); ++i) {
  40.             for (int j = 0; j < graph[i]->neighbors.size(); j++) {
  41.                 if (indegree.find(graph[i]->neighbors[j]) == indegree.end()) {
  42.                     indegree[graph[i]->neighbors[j]] = 1;
  43.                 } else {
  44.                     indegree[graph[i]->neighbors[j]] += 1;
  45.                 }
  46.             }
  47.         }
  48.     }
  50.     void dfs(map<DirectedGraphNode*, int> &indegree, DirectedGraphNode *i,
  51.              vector<DirectedGraphNode*> &ret) {
  53.         ret.push_back(i);
  54.         indegree[i]--;
  55.         for (int j = 0; j < i->neighbors.size(); ++j) {
  56.             indegree[i->neighbors[j]]--;
  57.             if (indegree[i->neighbors[j]] == 0) {
  58.                 dfs(indegree, i->neighbors[j], ret);
  59.             }
  60.         }
  61.     }
  62. };

源码分析

C++中使用 unordered_map 可获得更高的性能，私有方法中使用引用传值。

复杂度分析

以 V 表示顶点数，E 表示有向图中边的条数。

首先获得节点的入度数，时间复杂度为 O(V+E), 使用了哈希表存储，空间复杂度为 O(V). 遍历图求得入度为0的节点，时间复杂度为 O(V). 仅在入度为0时调用 DFS，故时间复杂度为 O(V+E).

需要注意的是这里的 DFS 不是纯 DFS，使用了 BFS 的思想进行了优化，否则一个节点将被遍历多次，时间复杂度可能恶化为指数级别。

综上，时间复杂度近似为 O(V+E), 空间复杂度为 O(V).

题解2 - BFS

拓扑排序除了可用 DFS 求解外，也可使用 BFS, 具体方法为：

  1. 获得图中各节点的入度。
  2. BFS 首先遍历求得入度数为0的节点，入队，便于下一次 BFS。
  3. 队列不为空时，弹出队顶元素并对其邻接节点进行 BFS，将入度为0的节点加入到最终结果和队列中，重复此过程直至队列为空。

C++

  1. /**
  2.  * Definition for Directed graph.
  3.  * struct DirectedGraphNode {
  4.  *     int label;
  5.  *     vector<DirectedGraphNode *> neighbors;
  6.  *     DirectedGraphNode(int x) : label(x) {};
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     /**
  12.      * @param graph: A list of Directed graph node
  13.      * @return: Any topological order for the given graph.
  14.      */
  15.     vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
  16.         vector<DirectedGraphNode*> result;
  17.         if (graph.size() == 0) return result;
  19.         map<DirectedGraphNode*, int> indegree;
  20.         // get indegree of all DirectedGraphNode
  21.         indeg(graph, indegree);
  22.         queue<DirectedGraphNode*> q;
  23.         // bfs
  24.         bfs(graph, indegree, q, result);
  26.         return result;
  27.     }
  29. private:
  30.     /** get indegree of all DirectedGraphNode
  31.      * 
  32.      */
  33.     void indeg(vector<DirectedGraphNode*> &graph, 
  34.                   map<DirectedGraphNode*, int> &indegree) {
  36.         for (int i = 0; i < graph.size(); ++i) {
  37.             for (int j = 0; j < graph[i]->neighbors.size(); j++) {
  38.                 if (indegree.find(graph[i]->neighbors[j]) == indegree.end()) {
  39.                     indegree[graph[i]->neighbors[j]] = 1;
  40.                 } else {
  41.                     indegree[graph[i]->neighbors[j]] += 1;
  42.                 }
  43.             }
  44.         }
  45.     }
  47.     void bfs(vector<DirectedGraphNode*> &graph, map<DirectedGraphNode*, int> &indegree,
  48.              queue<DirectedGraphNode *> &q, vector<DirectedGraphNode*> &ret) {
  50.         for (int i = 0; i < graph.size(); ++i) {
  51.             if (indegree[graph[i]] == 0) {
  52.                 ret.push_back(graph[i]);
  53.                 q.push(graph[i]);
  54.             }
  55.         }
  57.         while (!q.empty()) {
  58.             DirectedGraphNode *cur = q.front();
  59.             q.pop();
  60.             for(int j = 0; j < cur->neighbors.size(); ++j) {
  61.                 indegree[cur->neighbors[j]]--;
  62.                 if (indegree[cur->neighbors[j]] == 0) {
  63.                     ret.push_back(cur->neighbors[j]);
  64.                     q.push(cur->neighbors[j]);
  65.                 }
  66.             }
  67.         }
  68.     }
  69. };

源码分析

C++中在判断入度是否为0时将对 map 产生副作用，在求入度数时只有入度数大于等于1才会出现在 map 中，故不在 map 中时直接调用 indegree 方法将产生新的键值对，初始值为0，恰好满足此题需求。

复杂度分析

同题解1 的分析，时间复杂度为 O(V+E), 空间复杂度为 O(V).

Reference