This post is completed by 1 user

  • 0
 Add to List
Medium

Check If Given Undirected Graph is a tree

Objective: Given an undirected graph, Write an algorithm to determine whether its tree or not.

An undirected graph is a tree if it has properties mentioned below

  1. There is no cycle present in the graph.
  2. The graph is connected. (All the vertices in the graph are connected)

Example:

Recommended articles to read before continue reading

  1. Detect Cycle in an Undirected Graph using DFS.
  2. Check if Given Directed Graph is disconnected

Approach: 

Do DFS from any vertex. (please read DFS here), During DFS, for any current vertex X (currently visiting vertex) if there an adjacent vertex Y is present which is already visited and Y is not a direct parent of X then there is a cycle in the graph. If Cycle is present that means the graph is not a tree. If the cycle is not present then check whether the graph is connected. No need to do the DFS again to determine that, use the visited[] array filled during checking the cycle, if all the vertices are true in visited[] array means graph is connected and graph is tree else graph is not the tree.  

Code:


Output:

Vertex connected from vertex: 0
->1
Vertex connected from vertex: 1
->3->0
Vertex connected from vertex: 2
->3
Vertex connected from vertex: 3
->4->2->1
Vertex connected from vertex: 4
->3
Given Graph is Tree
----------------------------
Vertex connected from vertex: 0
->4->1
Vertex connected from vertex: 1
->3->0
Vertex connected from vertex: 2
->3
Vertex connected from vertex: 3
->4->2->1
Vertex connected from vertex: 4
->0->3
Given Graph is not Tree
----------------------------
Vertex connected from vertex: 0
->1
Vertex connected from vertex: 1
->3->0
Vertex connected from vertex: 2
->3
Vertex connected from vertex: 3
->2->1
Vertex connected from vertex: 4

Given Graph is not Tree

Reference: GeeksforGeeks

Also Read: