# Topological Sorting

## Problem

### 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]
...


#### Challenge

Can you do it in both BFS and DFS?

## 题解1 - DFS(统计节点入度数)

1. 找出不依赖其他顶点的顶点，即入度为0，这一定是符合要求的某一个拓扑排序的第一个顶点。
2. 在图中去掉入度为 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);
// 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);
}
}
}
};


### Java

/**
* Definition for Directed graph.
* class DirectedGraphNode {
*     int label;
*     ArrayList<DirectedGraphNode> neighbors;
*     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/

public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> sorting = new ArrayList<>();
Map<DirectedGraphNode, Integer> inDegreeMap = getIndegreeMap(graph);
for (Map.Entry<DirectedGraphNode, Integer> degreeMap : inDegreeMap.entrySet()) {
if (degreeMap.getValue() == 0) {
dfs(inDegreeMap, degreeMap.getKey(), sorting);
}
}

return sorting;
}

private Map<DirectedGraphNode, Integer> getIndegreeMap(ArrayList<DirectedGraphNode> graph) {
Map<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
for (DirectedGraphNode node : graph) {
inDegreeMap.putIfAbsent(node, 0);
for (DirectedGraphNode neighbor : node.neighbors) {
inDegreeMap.put(neighbor, inDegreeMap.getOrDefault(neighbor, 0) + 1);
}
}

return inDegreeMap;
}

private void dfs(Map<DirectedGraphNode, Integer> inDegreeMap, DirectedGraphNode node, List<DirectedGraphNode> result) {

inDegreeMap.put(node, inDegreeMap.get(node) - 1);
for (DirectedGraphNode neighbor : node.neighbors) {
inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
if (inDegreeMap.get(neighbor) == 0) {
dfs(inDegreeMap, neighbor, result);
}
}
}
}


### 源码分析

C++中使用 unordered_map 可获得更高的性能，私有方法中使用引用传值。在 dfs 递归的过程中，将节点加入到最终结果后需要对其入度减一，否则在上层循环邻居节点时会有重复。这里的 dfs 是剪枝过后的 DFS, 因为这里只处理入度为 0 的节点。另外在第一次求各节点的入度数时，需要先初始化为0，否则会漏掉部分入度为0的节点。

## 题解2 - BFS

1. 获得图中各节点的入度。
2. BFS 首先遍历求得所有入度数为0的节点，入队，便于下一次 BFS
3. 队列不为空时，弹出队顶元素并对其邻接节点入度数减一，将入度为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]);
}
}
}
}
};


### Java

/**
* Definition for Directed graph.
* class DirectedGraphNode {
*     int label;
*     ArrayList<DirectedGraphNode> neighbors;
*     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/

public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();

if (graph == null || graph.size() == 0) return result;

Map<DirectedGraphNode, Integer> map = getIndegreeMap(graph);
for (Map.Entry<DirectedGraphNode, Integer> entry : map.entrySet()) {
if (entry.getValue() == 0) {
queue.offer(entry.getKey());
}
}

bfs(queue, map, result);

return result;
}

private Map<DirectedGraphNode, Integer> getIndegreeMap(ArrayList<DirectedGraphNode> graph) {
Map<DirectedGraphNode, Integer> map = new HashMap<>();

for (DirectedGraphNode node : graph) {
map.putIfAbsent(node, 0);
for (DirectedGraphNode neighbor : node.neighbors) {
map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
}
}

return map;
}

private void bfs(Queue<DirectedGraphNode> queue, Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> result) {

while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode neighbor : node.neighbors) {
map.put(neighbor, map.get(neighbor) - 1);
if (map.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
}
}


### 源码分析

C++中在判断入度是否为0时将对 map 产生副作用，在求入度数时只有入度数大于等于1才会出现在 map 中，故不在 map 中时直接调用 indegree 方法将产生新的键值对，初始值为0，恰好满足此题需求。与 DFS 的解法不同，在 bfs 的实现中可以不对已加入到最终结果的节点入度数减一，因为没有上一层循环了。

## 题解3 - DFS(递归保证局部拓扑排序)

### Java

/**
* Definition for Directed graph.
* class DirectedGraphNode {
*     int label;
*     ArrayList<DirectedGraphNode> neighbors;
*     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/

public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> result = new ArrayList<>();

if (graph == null || graph.size() == 0) return result;

Set<DirectedGraphNode> visited = new HashSet<>();
Deque<DirectedGraphNode> stack = new ArrayDeque<>();

for (DirectedGraphNode node : graph) {
dfs(node, visited, stack);
}

while (!stack.isEmpty()) {
}

return result;
}

private void dfs(DirectedGraphNode root,
Set<DirectedGraphNode> visited,
Deque<DirectedGraphNode> stack) {

if (!visited.contains(root)) {
for (DirectedGraphNode neighbor : root.neighbors) {
dfs(neighbor, visited, stack);
}
stack.offerFirst(root);
}
}
}