Testing whether a graph is a tree

Question

In the input specification N the number of nodes and M the number of edges are given . So the first simple check is that M should be equal to N-1 otherwise it simply can't be a tree.

What I did next was just a DFS in which I see that whether during the DFS we come across a visited a node again ( different from the parent node, by parent node I mean the node which has called the dfs of the next node adjacent to it ) then it means that we have a cycle and it isn't a tree . But apparently my solution keeps on getting a wrong answer . I am posting the code but only the snippets that are important . I am storing the graph as a adjacency list and I am posting the function isTree() which tests whether it is a tree or not ? What is the correct logic ?

#include <iostream>
#include <list> 
using namespace std;

    // Graph class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
    bool isTreeUtil(int v, bool visited[],int parent);
public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    bool isTree();   // Tells whether the given graph is a tree or not
    void printGraph();
};

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

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
    adj[w].push_back(v);
}

bool Graph::isTreeUtil(int v, bool visited[],int parent)
{
    //int s_v = v;
    visited[v] = true;
    list<int>::iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i])
            isTreeUtil(*i,visited,v);
        else {
            if (*i != parent && visited[*i])
                return false;
        }
    }

    return true;
 }

bool Graph::isTree() {
    bool *visited = new bool[V+1];
    for(int i = 1; i < V+1; i++)
        visited[i] = false;

    visited[1] = true;  // marking the first node as visited
    for(int i = 1; i < V+1; i++)
        visited[i] = false;
    int parent = -1;   // initially it has no parent
    //list<int> :: iterator i;
    //for (i = adj[v].begin(); i != adj[v].end(); ++i)
    return isTreeUtil(1, visited, parent);
}

void Graph::printGraph() {
    for (int i = 1;i <= this->V; i++) {
        cout << i << "->";
        list<int>::iterator j;
        for (j = adj[i].begin(); j != adj[i].end(); ++j) {
            cout << *j << "->";
        }
        cout << "\n";
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    Graph G(N);
    int v, w;
    int m = 0;
    while (m < M) {
        cin >> v >> w;
        G.addEdge(v,w);
        m++;
    }

    if (M != N-1) {
        cout << "NO\n";
    else if (G.isTree())
        cout << "YES\n";
    else
        cout << "NO\n"; 
}

Answer 1

I took your code, compiled, and ran it on my machine. When implementing a graph, there are important specs to consider. When you choose to obey a spec, it is generally good practice to enforce that spec in your code.

It is already clear that the graph has 2-way edges, though it does not hurt to specifically mention this.

Allow Duplicate Edges? Your program allows me to make edge (1,2) and then another edge (1,2) and count it as 2 edges. This makes your conditional M != N-1 an insufficient check. Either disallow duplicate edges or account for them in your algorithm (currently, a duplicate edge will cause your algorithm to return incorrectly).

Self Edges? Does your graph allow a vertex to have an edge to itself? If so, should the self-path invalidate the tree (perhaps a self-loop is legal because in a tree, every node can access itself)? Currently, self edges also break your algorithm.

To help you, here is my revised implementation of addEdge() that disallows duplicate edges and disallows self-loops. As a bonus it also checks for array bounds ;) Please note that the additional include, and the change in function signature (it now returns a bool).

#include <algorithm>

bool Graph::addEdge(int v, int w)
{
    // sanity check to keep us from seg faulting
    if (v < 1 || v > this->V || w < 1 || w > this->V) {
        return false;
    }
    // no self-edges
    if (w == v) {
        return false;
    }
    // no duplicate edges allowed either
    std::list<int>::iterator findV = std::find(adj[v].begin(), adj[v].end(), w);
    std::list<int>::iterator findW = std::find(adj[w].begin(), adj[w].end(), v);
    if (findV != adj[v].end() || findW != adj[w].end()) {
        return false;
    }

    adj[v].push_back(w); // Add w to v’s list.
    adj[w].push_back(v);
    return true;
}

I hope this helps. If this is an assignment, you should review the write-up. They must have specified these cases if your implementation was auto-graded. As @congusbongus mentioned, your algorithm also fails in the case of a disconnected node.

Please note that you also have to revise the main() method in order for my implementation to work. Change this part of the function:

while (m < M) {
    cout << "Create Edge from x to y" << endl;
    cin >> v >> w;
    if (!G.addEdge(v,w)) {
        cout << ">>Invalid edge not added" << endl;
    } else {
        cout << ">>Successfully added edge" << endl;
        m++;
    }
}

Answer 2

it runs for all the simple test cases I drew on paper but when submitting it fails !

Sounds like some auto-marking system for homework right? If you had access to the exact test cases, then the problem would be obvious. In this case it's probably not available, so we can only speculate.

In my experience, most failures of this kind are due to missed boundary cases. You say you check for number of edges = number of nodes - 1, but have you also considered the following?

• All nodes connected
• No more than one edge per pair of nodes

That is, is your program prepared to return "NO" for this?

     _
    / \
o  o---o

Nodes: 3, edges: 2