C++ Program to Check if a 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.

Here is source code of the C++ Program to Check if an Directed Graph is a Tree or Not Using DFS. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#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.

```
}
```
```
 
```

// This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212

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.

// This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212

```
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;
```
```
}
```

Output:

$ g++ DirectedTree.cpp
$ a.out
 
Directed Graph isn't a tree
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Find the Edge Connectivity of a Graph

» Next - C++ Program to Find the Largest Clique in a Planar Graph

Next Steps:

Get Free Certificate of Merit in C++ Programming
Participate in C++ Programming Certification Contest
Become a Top Ranker in C++ Programming
Take C++ Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Computer Science MCQs
Apply for Information Technology Internship
Buy Computer Science Books
Buy Programming Books
Apply for C++ Internship

Recommended Articles: