How would you check if a graph is a tree?

Question

Accepted Answer

A graph is a tree if it is connected and doesn’t have a cycle. To formally define these terms:

- A graph is connected if there’s a path between every pair of vertices.

- A graph has a cycle if there’s a non-empty trail in which the start and end vertices are the same.

So we can implement the following algorithm to check, if a graph is a tree:

1. Check if there is a cycle in the provided graph

2. If there is a cycle, the graph is not a tree.

3. If there is no cycle, check if the graph is connected.

4. If the graph is connected, it is a tree.

Here are the details of each step:

1. **Checking for Cycle** - Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestors in the tree produced by DFS. You can use the below pseudo-code to detect cycle:

def isCyclicUtil(v, visited, parent):
 
    visited[v] = True
 
    for i in graph[v]:
         
        if visited[i] == False:
            if isCyclicUtil(i, visited, v) == True:
                return True
        elif parent != i:
            return True
 
    return False
 
def isCyclic():
   
    visited =[False]*(len(graph))
 
    for i in range(len(graph)):
        if visited[i] == False:
            if isCyclicUtil(i, visited, -1) == True:
                return True
 
    return False

2. **Checking for connected graph** - While doing DFS traversal mark every visited vertex, if we get any vertex which is not visited, means graph is not connected.

def DFS(v, visited):
 
    visited[v] = True
 
    for i in graph[v]:
        if visited[i] == False:
            DFS(i, visited)
 
def isConnected():
   
    visited =[False]*(len(graph))
 
    DFS(0, visited)
 
    for i in range(len(graph)):
        if visited[i] == False:
            return False
 
    return True

The graph is a tree if it passes both these checks.

The time complexity for both these operations is O(V+E) where V is the number of vertices in the graph and E is the number of edges since we are using DFS traversal.