How do I implement topological sort and cycle detection in C++?

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering. To implement topological sorting in C++, we can use depth-first search (DFS) and maintain a visited status for each vertex to detect cycles.

Topological Sort, Cycle Detection, C++, Directed Graph, Depth-First Search, Algorithm

This code demonstrates how to implement topological sorting and cycle detection in a directed graph using C++.


        #include 
        #include 
        #include 
        #include 
        using namespace std;

        class Graph {
        private:
            int V;
            list *adj;

            bool isCyclicUtil(int v, vector& visited, vector& recStack) {
                visited[v] = true;
                recStack[v] = true;
                
                for (auto i : adj[v]) {
                    if (!visited[i] && isCyclicUtil(i, visited, recStack))
                        return true;
                    else if (recStack[i])
                        return true;
                }
                recStack[v] = false;
                return false;
            }

        public:
            Graph(int V) {
                this->V = V;
                adj = new list[V];
            }

            void addEdge(int v, int w) {
                adj[v].push_back(w);
            }

            bool isCyclic() {
                vector visited(V, false);
                vector recStack(V, false);
                for (int i = 0; i < V; i++) {
                    if (!visited[i]) {
                        if (isCyclicUtil(i, visited, recStack))
                            return true;
                    }
                }
                return false;
            }

            void topologicalSortUtil(int v, vector& visited, stack& Stack) {
                visited[v] = true;
                for (auto i : adj[v]) {
                    if (!visited[i])
                        topologicalSortUtil(i, visited, Stack);
                }
                Stack.push(v);
            }

            void topologicalSort() {
                stack Stack;
                vector visited(V, false);
                
                for (int i = 0; i < V; i++) {
                    if (!visited[i])
                        topologicalSortUtil(i, visited, Stack);
                }

                while (!Stack.empty()) {
                    cout << Stack.top() << " ";
                    Stack.pop();
                }
            }
        };

        int main() {
            Graph g(6);
            g.addEdge(5, 2);
            g.addEdge(5, 0);
            g.addEdge(4, 0);
            g.addEdge(4, 1);
            g.addEdge(3, 1);
            g.addEdge(2, 3);
            
            if (g.isCyclic())
                cout << "Graph has a cycle" << endl;
            else {
                cout << "Topological Sort: ";
                g.topologicalSort();
            }
            return 0;
        }

How do I implement topological sort and cycle detection in C++?

Popular Topics

Recent Languages

How do I implement topological sort and cycle detection in C++?

Related Questions

Popular Topics

Recent Languages