# 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

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