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:
1. Construct the graph with adjacency matrix or adjacency list
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][0]; int endNode = list[i][1]; //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 {}; } }