|Algo| Topological Sort

zhuzii,

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 {};
    }
}

Ref.
1. Topological Sorting
2. pattern – Topological Sort