> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/127.topological-sorting.md).

# 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;
    }
```