7. Topological Sort

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u v) , vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For the sample graph shown above, one of the possible ordering of courses is: C6 ➔ C4 ➔ C1 ➔ C5 ➔ C2 ➔ C3 and another possible ordering of subjects is C6 ➔ C4 ➔ C5 ➔ C1 ➔ C2 ➔ C3.

Using DFS

    void topologicalSort(vector<int> v[], vector<bool> &vs, stack<int> &s, int src)
    {

        vs[src] = 1;

        for (int i = 0; i < v[src].size(); i++)
        {
            int node = v[src][i];

            if (!vs[node])
            {
                topologicalSort(v, vs, s, node);
            }
        }

        s.push(src);
        return;
    }

Using Node Indegree

    vector<int> bfs(vector<int> v[], vector<int> &indeg)
    {
        queue<int> q;
        
        for (int i = 0; i < indeg.size(); i++)
        {
            if (indeg[i] == 0)
            {
                q.push(i);
            }
        }
        
        vector<int> res;
        while (!q.empty())
        {
            int x = q.front();
            res.push_back(x);
            q.pop();

            for (int i = 0; i < v[x].size(); i++)
            {
                indeg[v[x][i]] = indeg[v[x][i]] - 1;
                if (indeg[v[x][i]] == 0)
                {
                    q.push(v[x][i]);
                }
            }
        }
        return res;
    }