Topological Sort BFS | Easiest Explanation Ever

Complexities:
TC: O(V+E)
SC: O(1)

vector<int> topoSort(int N, vector<int> adj[]){ // topological sort  // N = number of vertices in graph // adj = adjacency list
    queue<int> q; //  queue of vertices with no incoming edges
    vector<int> inDegree(N,0); // inDegree[i] = number of incoming edges to vertex i
    for(int i=0;i<N;i++){
        for(auto it:adj[i]){ // for each edge (i,j) in graph // it = j in this case
            inDegree[it]++; // inDegree[i] = # of edges that point to i
        }
    }
    for(int i=0;i<N;i++){
        if(inDegree[i]==0){ // if there is no edge pointing to i
            q.push(i);
        }
    }
    vector<int> topo; 
    while(!q.empty()){ // while there is still a node with no incoming edges
        int curr = q.front(); 
        q.pop(); // remove the node from the queue
        topo.push_back(curr); // add the node to the topo vector
        for(auto it:adj[curr]){ // for each node that points to curr
            inDegree[it]--; // decrement the inDegree of that node
            if(inDegree[it]==0){ // if the inDegree of that node is 0
                q.push(it); // add it to the queue
            }
        }
    }
    return topo; // return the topo vector
}
Comments (0)