How to determine if a given directed graph is a tree

Question

The input to the program is the set of edges in the graph. For e.g. consider the following simple directed graph:

a -> b -> c

The set of edges for this graph is

{ (b, c), (a, b) }

So given a directed graph as a set of edges, how do you determine if the directed graph is a tree? If it is a tree, what is the root node of the tree?

First of I'm looking at how will you represent this graph, adjacency list/ adjacency matrix / any thing else? How will utilize the representation that you have chosen to efficiently answer the above questions?

Edit 1:

Some people are mentoning about using DFS for cycle detection but the problem is which node to start the DFS from. Since it is a directed graph we cannot start the DFS from a random node, for e.g. if I started a DFS from vertex 'c' it won't proceed further since there is no back edge to go to any other nodes. The follow up question here should be how do you determine what is the root of this tree.

Answer 1

Here's a fairly direct method. It can be done with either an adjacency matrix or an edge list.

1. Find the set, R, of nodes that do not appear as the destination of any edge. If R does not have exactly one member, the graph is not a tree.

2. If R does have exactly one member, r, it is the only possible root.

3. Mark r.

4. Starting from r, recursively mark all nodes that can be reached by following edges from source to destination. If any node is already marked, there is a cycle and the graph is not a tree. (This step is the same as a previously posted answer).

5. If any node is not marked at the end of step 3, the graph is not a tree.

If none of those steps find that the graph is not a tree, the graph is a tree with r as root.

It's difficult to know what is going to be efficient without some information about the numbers of nodes and edges.

Answer 2

There are 3 properties to check if a graph is a tree:

• (1) The number of edges in the graph is exactly one less than the number of vertices |E| = |V| - 1
• (2) There are no cycles
• (3) The graph is connected

I think this example algorithm can work in the cases of a directed graph:

 # given a graph and a starting vertex, check if the graph is a tree
 def checkTree(G, v):

    # |E| = |V| - 1
    if edges.size != vertices.size - 1:
        return false;

    for v in vertices:
        visited[v] = false;

    hasCycle = explore_and_check_cycles(G, v);

    # a tree is acyclic
    if hasCycle:
        return false;

    for v in vertices:
        if not visited[v]: # the graph isn't connected
            return false;

    # otherwise passes all properties for a tree
    return true;

# given a Graph and a vertex, explore all reachable vertices from the vertex
# and returns true if there are any cycles
def explore_and_check_cycles(G, v):
    visited[v] = true;

    for (v, u) in edges:
        if not visited[u]:
            return explore_and_check_cyles(G, u)
        else: # a backedge between two vertices indicates a cycle
            return true

    return false

Sources: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani http://www.cs.berkeley.edu/~vazirani/algorithms.html

Answer 3

start from the root, "mark" it and then go to all children and repeat recursively. if you reach a child that is already marked it means that it is not a tree...

Answer 4

Note: By no means the most efficient way, but conceptually useful. Sometimes you want efficiency, sometimes you want an alternate viewpoint for pedagogic reasons. This is most certainly the later.

Algorithm: Starting with an adjacency matrix A of size n. Take the matrix power A**n. If the matrix is zero for every entry you know that it is at least a collection of trees (a forest). If you can show that it is connected, then it must be a tree. See a Nilpotent matrix. for more information.

To find the root node, we assume that you've shown the graph is a connected tree. Let k be the the number of times you have to raise the power A**k before the matrix becomes all zero. Take the transpose to the (k-1) power A.T ** (k-1). The only non-zero entry must be the root.

Analysis: A rough worse case analysis shows that it is bounded above by O(n^4), three for the matrix multiplication at most n times. You can do better by diagonalizing the matrix which should bring it down to O(n^3). Considering that this problem can be done in O(n), O(1) time/space this is only a useful exercise in logic and understanding of the problem.

Answer 5

For a directed graph, the underlying undirected graph will be a tree if the undirected graph is acyclic and fully connected. The same property holds good if for the directed graph, each vertex has in-degree=1 except one having in-degree=0.

If adjacency-list representation also supports in-degree property of each vertex, then we can apply the above rule easily. Otherwise, we should apply a tweaked DFS to find no-loops for underlying undirected graph as well as that |E|=|V|-1.

Answer 6

Following is the code I have written for this. Feel free to suggest optimisations.

import java.util.*;
import java.lang.*;
import java.io.*;

class Graph
{
private static int V;
private static int adj[][];

static  void initializeGraph(int n)
{
    V=n+1;
    adj = new int[V][V];
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V ;j++)
        adj[i][j]= 0;
    }

}

static int isTree(int edges[][],int n)
{
    initializeGraph(n);

    for(int i=0;i< edges.length;i++)
    {
        addDirectedEdge(edges[i][0],edges[i][1]);
    }

    int root = findRoot();
    if(root == -1)
    return -1;
    boolean visited[] = new boolean[V];
    boolean isTree = isTree(root, visited, -1);
    boolean isConnected = isConnected(visited);
    System.out.println("isTree= "+ isTree + " isConnected= "+ isConnected);
    if(isTree && isConnected)
    return root;
    else 
    return -1;

}

static  boolean isTree(int node, boolean visited[], int parent)
{
//  System.out.println("node =" +node +" parent" +parent);
    visited[node] = true;int j;

    for(j =1;j<V;j++)
    {
    //  System.out.println("node =" +node + " j=" +j+ "parent" + parent);
        if(adj[node][j]==1)
        {
            if(visited[j])
            {
            //  System.out.println("returning false for j="+ j);
                return false;
            }
            else
            {   //visit all adjacent vertices
                boolean child = isTree(j, visited, node);
                if(!child)
                {
                //  System.out.println("returning false for j="+ j + " node=" +node);
                    return false;   
                }
            }

        }
    }
    if(j==V)
    return true;
    else
    return false;
}

static int findRoot()
{
    int root =-1, j=0,i;
    int count =0;
    for(j=1;j<V ;j++)
    {
        count=0;
        for(i=1 ;i<V;i++)
        {
            if(adj[i][j]==1)
            count++;
        }
    //  System.out.println("j"+j +" count="+count);
        if(count==0)
        {
        //  System.out.println(j);
            return j;   
        }
    }
    return -1;
}

static void addDirectedEdge(int s, int d)
{
//  System.out.println("s="+ s+"d="+d);
    adj[s][d]=1;
}

static boolean isConnected(boolean visited[])
{
    for(int i=1; i<V;i++)
    {
        if(!visited[i])
        return false;
    }
    return true;
}

public static void main (String[] args) throws java.lang.Exception
{
    int edges[][]= {{2,3},{2,4},{3,1},{3,5},{3,7},{4,6}, {2,8}, {8,9}};
    int n=9;
    int root = isTree(edges,n);
    System.out.println("root is:" + root);

    int edges2[][]= {{2,3},{2,4},{3,1},{3,5},{3,7},{4,6}, {2,8}, {6,3}};
    int n2=8;
    root = isTree(edges2,n2);
    System.out.println("root is:" + root);
   }
}