C++ Program to Check whether Directed Graph is Connected using DFS

Code:

#include   iostream
#include   list
#include   stack
using namespace std;
/*
 * Class Declaration
 */
class Graph
{
    private:
        int V;
        list *adj;
        void DFSUtil(int v, bool visited[]);
    public:
    Graph(int V)
    {
        this->V = V;
        adj = new list[V];
    }
    ~Graph()
    {
        delete [] adj;
    }
    void addEdge(int v, int w);
    bool isConnected();
    Graph getTranspose();
};

/*
 * A recursive function to print DFS starting from v
 */
void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true;
    list::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

/*
 *  Function that returns reverse (or transpose) of this graph
 */
Graph Graph::getTranspose()
{
    Graph g(V);
    for (int v = 0; v < V; v++)
    {
        list::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            g.adj[*i].push_back(v);
        }
    }
    return g;
}
/*
 * Add Edge to connect v and w
 */
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
}
/*
 * Check if Graph is Connected
 */
bool Graph::isConnected()
{
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
    DFSUtil(0, visited);
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
             return false;
    Graph gr = getTranspose();
    for(int i = 0; i < V; i++)
        visited[i] = false;
    gr.DFSUtil(0, visited);
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
             return false;
    return true;
}
/*
 * Main Contains Menu
 */
int main()
{
    Graph g1(5);
    g1.addEdge(0, 1);
    g1.addEdge(1, 2);
    g1.addEdge(2, 3);
    g1.addEdge(3, 0);
    g1.addEdge(2, 4);
    g1.addEdge(4, 2);
    if (g1.isConnected())
        cout<<"The Graph is Conneted"<
    else
        cout<<"The Graph is not Connected"<

    Graph g2(4);
    g2.addEdge(0, 1);
    g2.addEdge(1, 2);
    g2.addEdge(2, 3);
    if (g2.isConnected())
        cout<<"The Graph is Connected"<
    else
        cout<<"The Graph is not Connected"<
    return 0;
}


Output:

The Graph is Connected
The Graph is Not Connected

------------------
(program exited with code: 0)
Press return to continue



More C++ Programs: