Graph Topological sort

Topological sorting is an ordering of the vertices of a directed graph such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. In simpler terms, it is a linear ordering of the vertices such that for every directed edge, the source vertex comes before the destination vertex.

Topological sorting is applicable only to Directed Acyclic Graphs (DAGs). If the graph has a cycle, it cannot have a topological ordering because there is no way to arrange the vertices in a linear order respecting the directed edges.

Topological sorting has various practical applications, including task scheduling, build systems, and dependency resolution. In a task scheduling context, vertices represent tasks, and directed edges represent dependencies between tasks.

A DAG can have multiple valid topological orders. This is because there may be several vertices with no incoming edges, and they can be processed in any order.

Topological Sort Steps:

Initialize an empty stack to store the topological order.
Perform a DFS traversal on the graph.
When a vertex finishes processing (i.e., all its neighbors are visited), push it onto the stack.
The topological order is obtained by popping elements from the stack.

After the DFS traversal and stack operations, it’s essential to check if all vertices have been visited. If not, the graph contains cycles, and a topological ordering is not possible.

   Example to illustrate topological sorting:

   Graph:
   1  ->  2  ->  4
    \      \
      v      v
       3 ----> 5

Topological Order: 1 3 2 4 5

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

class Graph {
private:
    int vertices;
    std::vector<std::vector<int>> adjacencyList;

public:
    Graph(int v) : vertices(v), adjacencyList(v) {}

    void addEdge(int u, int v) {
        adjacencyList[u].push_back(v);
    }

    void topologicalSortUtil(int v, std::unordered_set<int>& visited, std::stack<int>& stack) {
        visited.insert(v);

        for (int neighbor : adjacencyList[v]) {
            if (visited.find(neighbor) == visited.end()) {
                topologicalSortUtil(neighbor, visited, stack);
            }
        }

        stack.push(v);
    }

    void topologicalSort() {
        std::stack<int> stack;
        std::unordered_set<int> visited;

        for (int i = 0; i < vertices; ++i) {
            if (visited.find(i) == visited.end()) {
                topologicalSortUtil(i, visited, stack);
            }
        }

        // Print the topological order
        std::cout << "Topological Sort: ";
        while (!stack.empty()) {
            std::cout << stack.top() << " ";
            stack.pop();
        }
        std::cout << std::endl;
    }
};

int main() {
    Graph graph(6);
    graph.addEdge(5, 2);
    graph.addEdge(5, 0);
    graph.addEdge(4, 0);
    graph.addEdge(4, 1);
    graph.addEdge(2, 3);
    graph.addEdge(3, 1);

    std::cout << "Graph edges:\n";
    std::cout << "5 -> 2\n";
    std::cout << "5 -> 0\n";
    std::cout << "4 -> 0\n";
    std::cout << "4 -> 1\n";
    std::cout << "2 -> 3\n";
    std::cout << "3 -> 1\n";

    graph.topologicalSort();

    return 0;
}

Output:

Graph edges:
5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1
Topological Sort: 5 4 2 3 1 0