In this article, we will check if an undirected graph is a tree or not. A graph is an abstract Data Structure that consists of a set of vertices (nodes) and a set of pairs containing these vertices. A pair represents an edge (line/ connection) between two vertices. If the graph is undirected, the pairs are unordered, which means that both vertices are connected. In a directed graph, pairs are ordered; the edge (v1, v2) indicates a connection between v1 and v2, but not the other way around.

A tree, on the other hand, is a type of undirected graph that has the following two properties:

1. There are no cycles; every node has only one parent.
2. The graph is connected, i.e., we can go from every vertex to any other vertex in the graph.

Simply put, a tree is a connected acyclic undirected graph.

How to determine if an Undirected Graph is a Tree or Not Using DFS

So, to determine if an undirected graph is a tree or not, we have to check for the above two properties.  We will use the Depth First Search (DFS) approach. The steps of the solution are as follows:

Initially, in our main function, we create an array (a dictionary or hash table) to keep track of the visited nodes. In the beginning, it is false for every node.

Then, we call a recursive function to detect whether there is a cycle in the graph or not. Initially, we pass a node of the graph as the current vertex (curr_vertex), visited variable, NULL as the parent since this is the first node to be passed.
[adinserter block=”2″] Now, the recursive function marks the curr_vertex as visited. Then, it iterates over the adjacent nodes of the current vertex.

• If the adjacent node is unvisited, then it calls itself with the adjacent vertex as the curr_vertex, visited variable, and the current vertex as the parent. If this call returns false (indicating no cycle), then the function continues. Otherwise, the function returns true (indicating a loop) as well.
• However, if the adjacent node is visited but similar to the parent, nothing happens. The function moves to the next neighboring vertex if there is any.

In the above figure, first, node 5 is visited, and then the recursive function gets called with node 1 as the current vertex and 5 as the parent. Here, 5 is adjacent to 1, and it is already visited. However, it does not imply a cycle as it is the parent.

• Otherwise, there is a cycle in the graph, and the function returns true.

First, node 2 is visited, then node 5, and finally, the recursive function gets called with node 1 as the current vertex and 5 as the parent. Here, 2 is already visited and is not a parent of 1 specifying a cycle in the graph.

• Finally, if we successfully iterate over all adjacent nodes, we return false as no cycle got detected.

If a cycle gets detected in a graph, we return false from the main function as there is no need to check further about the graph’s connectivity. However, if there is no cycle, we call another method with the visited variable (it has now updated data from the recursive function) to see if the graph is connected. If there are any unvisited vertices, then the graph is not connected, and thus, not a tree. However, if all the vertices are visited, implying a connected graph, we will return true as there isn’t a cycle and the graph is connected.

Implementation

The implementation of the above solution is given below:

class Graph:
  def __init__(self):
    self.vertices = []
    self.graph = {}
  
  #add an isolated vertex in the graph
  def add_isolated_vertex(self, vertex):
    if vertex in self.vertices:
      raise KeyError(f"Vertex {vertex} already exists in the graph")
    else:
      self.vertices.append(vertex)
      self.graph[vertex] = [] #add isolated vertex in th graph

  #add an edge to the graph
  def add_edge(self, edge): #edge is passed as an tuple (v1, v2)
    v1 = edge[0]
    v2 = edge[1]

    #add an edge v1->v2
    if self.graph.get(v1, None): #v1 already exists as a vertex in the graph
      self.graph[v1].append(v2)
    else:
      self.graph[v1] = [v2]
      self.vertices.append(v1) 

    #add an edge v2->v1
    if self.graph.get(v2, None): #v2 already exists as a vertex in the graph
      self.graph[v2].append(v1)
    else:
      self.graph[v2] = [v1]
      self.vertices.append(v2)

  #display all the edges in the graph
  def display_edges(self):
    print("---------Graph---------")
    for vertex1 in self.graph.keys():
      if len(self.graph[vertex1]) == 0:
        print("Isolated vertex", vertex1)
      for vertex2 in self.graph[vertex1]:
        print(f"edge {vertex1}-->{vertex2}")
  
  def is_cycle(self, curr_vertex, visited, parent):
    #mark the current node as visited
    visited[curr_vertex] = True

    #get the adjacent nodes
    adjacent_nodes = self.graph[curr_vertex]
    
    #iterate over adjacent nodes
    for adjacent in adjacent_nodes:
      if not visited[adjacent]:
        if self.is_cycle(adjacent, visited, curr_vertex): #recur for the adjacent node
          return True
      elif visited[adjacent] and adjacent == parent:  #adjacent node is parent
        continue
      else: #adjacent node is visited and not a parent, indicating a cycle
        return True
    
    return False
  
  #check if the graph is connected or not using the visited nodes info
  def is_connected(self, visited):
    for vertex in self.vertices:
      if not visited[vertex]:
        return False
    return True

  #check if the graph is a tree or not
  def is_tree(self):
    #create a dictionary to store information of visited node
    visited ={}
    for node in self.vertices:
      visited[node] = False

    #check for a cycle by passing a vertex from the graph
    cycle = self.is_cycle(self.vertices[0], visited, None)
    if cycle:
      return False

    #check if the graph is connected
    return self.is_connected(visited)

Now call the function:

graph_1 = Graph()
graph_1.add_edge((2, 0))
graph_1.add_edge((0, 1))
graph_1.add_edge((1, 3))
tree = graph_1.is_tree()
if tree:
  print("The given graph is a tree")
else:
  print("The given graph is not a tree")

Output

The given graph is a tree

Call the function using different parameters:

graph_2 = Graph()
graph_2.add_edge((2, 0))
graph_2.add_edge((0, 1))
graph_2.add_edge((1, 3))
graph_2.add_edge((2, 3))
tree = graph_2.is_tree()
if tree:
  print("The given graph is a tree")
else:
  print("The given graph is not a tree")

Output

The given graph is not a tree

graph_3 = Graph()
graph_3.add_edge((2, 0))
graph_3.add_edge((0, 1))
graph_3.add_edge((1, 3))
graph_3.add_isolated_vertex(4)
tree = graph_3.is_tree()
if tree:
  print("The given graph is a tree")
else:
  print("The given graph is not a tree")

Output

The given graph is not a tree