# 127.Topological Sorting

## 1.Description(Medium)

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.

**Clarification**

[Learn more about representation of graphs](http://www.lintcode.com/help/graph)

**Example**

For graph as follow:

![picture](https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcThE9AgZZszyhwe0o9qpp3VyizdIj9kWwMY50HiQEysXvkSLsoZ)

The topological order can be:

```
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
```

## 2.Code

图搜索相关的问题较为常见的解法是用[DFS](https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73093#\)，这里结合\[BFS]\(https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73093#)进行求解，分为三步走：

1. 统计各定点的入度——只需统计节点在邻接列表中出现的次数即可知。
2. 遍历图中各节点，找到入度为0的节点。
3. 对入度为0的节点进行递归[DFS](https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73093#)，将节点加入到最终返回结果中。

拓扑排序除了可用[DFS](https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73093#\)求解外，也可使用\[BFS]\(https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73093#), 还可以用BFS具体方法为：

1. 获得图中各节点的入度。存放在HashMap中，但是map中存放的是入度至少为1的点。
2. BFS首先遍历得到入度为0的点（不止一个，永不存在map中点得到），入队，进行下一次BFS
3. 队列不为空时，弹出队顶元素并对其邻接节点进行[BFS](https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73093#)，现将其入度-1，如果他的入度变成0，就加入最终结果和队列中，重复此过程直至队列为空。

```
class DirectedGraphNode {
          int label;
          ArrayList<DirectedGraphNode> neighbors;
          DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
      };
public class Solution_127 {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        //Indegree
        HashMap<DirectedGraphNode,Integer> map=new HashMap<>();
        for(DirectedGraphNode node: graph){
            for(DirectedGraphNode element: node.neighbors){
                if(map.containsKey(element)){
                    map.put(element,map.get(element)+1);
                }
                else{
                    map.put(element,1);
                }
            }
        }

        //队列放入度为0的点,但是入度为0的点可能不止一个,入度为0的点不存在map中
        Queue<DirectedGraphNode> queue=new LinkedList<DirectedGraphNode>();
        ArrayList<DirectedGraphNode> result=new ArrayList<DirectedGraphNode>();
        for(DirectedGraphNode node: graph){
            if(!map.containsKey(node)){
                queue.offer(node);
                result.add(node);
            }
        }

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/127.topological-sorting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.