# 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

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

**Example:**

Recommended articles to read before continue reading

**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

**is present which is already visited and**

*Y***is not a direct parent of**

*Y***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.**

*X***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