# |Algo| Topological Sort

In fact, Topological Sort is a BFS.
It is to solve the question which should list all path of graph.
But there are some conditions which users should understand.

Conditions:

1. Directive graph
2. No cycle
3. In order to list paths

Mental cultivation:
2. find the nodes whose order is zero as the sources(an queue).
(order == 0: no other node point to it, that is, it is the beginner)
3. Pick a node from the queue(sources),
push into the target(path list),
traverse into the graph to update the order of nodes, which are connect with the picked one.
If the updated node become an order zero node, push into queue(sources).
4. If queue(sources) is empty, end.

Examples:
207. Course Schedule
210. Course Schedule II
269 – Alien Dictionary

Template:

```class Solution {
public:
vector findOrder(int numCourses, vector>& prerequisites) {
unordered_map<int, vector<int>> graph;
unordered_map<int, int> order;
//construct graph
for(int i = 0; i < numCourses; i++){
graph[i] = {};
order[i] = 0;
}

//build the graph
for(int i = 0; i < list.size(); i++){
int startNode = list[i];
int endNode = list[i];

//startNode -> endNode
graph[startNode ].push_back(endNode);
order[endNode ]++;
}

//find the sources which has no any dependency
queue<int> sources;
for(auto& p: order) {
if(p.second == 0){
sources.push(p.first);
}
}

//generate the sequence of cources
vector<int> sortedList;
while(!sources.empty()){
int intSource = sources.front();
sources.pop();
sortedList.push_back(intSource );

for(auto& g:graph[intSource ]){
if(--order[g] == 0){
sources.push(g);
}
}
}

// If the size of topological order list is not equal to num
// Return false
if (sortedList.size() == num){
return sortedList;
}else{
return {};
}
}
```