C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Program to Check if an Directed Graph is a Tree or Not Using DFS



Program to Check if an Directed Graph is a Tree or Not Using DFS

This is a C++ Program to check whether an directed graph is tree or not. Graph is tree if it doesn't contain cycles.

    #include<iostream>

    #include <list>

    #include <limits.h>

    using namespace std;

    class Graph

    {

            int V; // No. of vertices

            list<int> *adj; // Pointer to an array containing adjacency lists

            bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()

        public:

            Graph(int V); // Constructor

            void addEdge(int v, int w); // to add an edge to graph

            bool isCyclic(); // returns true if there is a cycle in this graph

    };

    Graph::Graph(int V)

    {

        this->V = V;

        adj = new list<int> [V];

    }

    void Graph::addEdge(int v, int w)

    {

        adj[v].push_back(w); // Add w to v's list.

    }
 
    bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)

    {

        if (visited[v] == false)

        {

            // Mark the current node as visited and part of recursion stack

            visited[v] = true;

            recStack[v] = true;

            // Recur for all the vertices adjacent to this vertex

            list<int>::iterator i;

            for (i = adj[v].begin(); i != adj[v].end(); ++i)

            {

                if (!visited[*i] && isCyclicUtil(*i, visited, recStack))

                    return true;

                else if (recStack[*i])

                    return true;

            }

        }

        recStack[v] = false; // remove the vertex from recursion stack

        return false;

    }

    // Returns true if the graph contains a cycle, else false.

    bool Graph::isCyclic()

    {

        // Mark all the vertices as not visited and not part of recursion stack

        bool *visited = new bool[V];

        bool *recStack = new bool[V];

        for (int i = 0; i < V; i++)

        {

            visited[i] = false;

            recStack[i] = false;

        }

        // Call the recursive helper function to detect cycle in different DFS trees

        for (int i = 0; i < V; i++)

            if (isCyclicUtil(i, visited, recStack))

                return true;

        return false;

    }

    int main()

    {

        // Create a graph given in the above diagram

        Graph g(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

        if (g.isCyclic())

            cout << "Directed Graph isn't a tree";

        else

            cout << "Directed Graph is a tree";

        return 0;

    }