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:

- There are no cycles; every node has only one parent.
- 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.

`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

Blog Hero