Write a function that returns true if a given undirected graph is tree and false otherwise. For example, the following graph is a tree.

 

But the following graph is not a tree.

An undirected graph is tree if it has following properties.
1) There is no cycle.
2) The graph is connected.

For an undirected graph we can either use BFS or DFS to detect above two properties.

How to detect cycle in an undirected graph?
We can either use BFS or DFS. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle (See Detect cycle in an undirected graph for more details).

How to check for connectivity?
Since the graph is undirected, we can start BFS or DFS from any vertex and check if all vertices are reachable or not. If all vertices are reachable, then graph is connected, otherwise not.

[ad type=”banner”]

Java  Programming:

[pastacode lang=”java” manual=”%2F%2F%20A%20Java%20Program%20to%20check%20whether%20a%20graph%20is%20tree%20or%20not%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20directed%20graph%20using%20adjacency%0A%2F%2F%20list%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20private%20int%20V%3B%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%20%2F%2FAdjacency%20List%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20Graph(int%20v)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20adj%20%3D%20new%20LinkedList%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cv%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20adj%5Bi%5D%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20add%20an%20edge%20into%20the%20graph%0A%20%20%20%20void%20addEdge(int%20v%2Cint%20w)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20adj%5Bv%5D.add(w)%3B%0A%20%20%20%20%20%20%20%20adj%5Bw%5D.add(v)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20that%20uses%20visited%5B%5D%20and%20parent%0A%20%20%20%20%2F%2F%20to%20detect%20cycle%20in%20subgraph%20reachable%20from%20vertex%20v.%0A%20%20%20%20Boolean%20isCyclicUtil(int%20v%2C%20Boolean%20visited%5B%5D%2C%20int%20parent)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20Integer%20i%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20it%20%3D%20adj%5Bv%5D.iterator()%3B%0A%20%20%20%20%20%20%20%20while%20(it.hasNext())%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20it.next()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20an%20adjacent%20is%20not%20visited%2C%20then%20recur%20for%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20that%20adjacent%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(isCyclicUtil(i%2C%20visited%2C%20v))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20an%20adjacent%20is%20visited%20and%20not%20parent%20of%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20current%20vertex%2C%20then%20there%20is%20a%20cycle.%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(i%20!%3D%20parent)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Returns%20true%20if%20the%20graph%20is%20a%20tree%2C%20else%20false.%0A%20%20%20%20Boolean%20isTree()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%20and%20not%20part%0A%20%20%20%20%20%20%20%20%2F%2F%20of%20recursion%20stack%0A%20%20%20%20%20%20%20%20Boolean%20visited%5B%5D%20%3D%20new%20Boolean%5BV%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20call%20to%20isCyclicUtil%20serves%20multiple%20purposes%0A%20%20%20%20%20%20%20%20%2F%2F%20It%20returns%20true%20if%20graph%20reachable%20from%20vertex%200%0A%20%20%20%20%20%20%20%20%2F%2F%20is%20cyclcic.%20It%20also%20marks%20all%20vertices%20reachable%0A%20%20%20%20%20%20%20%20%2F%2F%20from%200.%0A%20%20%20%20%20%20%20%20if%20(isCyclicUtil(0%2C%20visited%2C%20-1))%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20we%20find%20a%20vertex%20which%20is%20not%20reachable%20from%200%0A%20%20%20%20%20%20%20%20%2F%2F%20(not%20marked%20by%20isCyclicUtil()%2C%20then%20we%20return%20false%0A%20%20%20%20%20%20%20%20for%20(int%20u%20%3D%200%3B%20u%20%3C%20V%3B%20u%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%20%20%20%20%20%20%20Graph%20g1%20%3D%20new%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(1%2C%200)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%203)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(3%2C%204)%3B%0A%20%20%20%20%20%20%20%20if%20(g1.isTree())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20is%20Tree%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20is%20not%20Tree%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g2%20%3D%20new%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(1%2C%200)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(2%2C%201)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%203)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(3%2C%204)%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(g2.isTree())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20is%20Tree%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20is%20not%20Tree%22)%3B%0A%20%0A%20%20%20%20%7D%0A%7D%0A%2F%2F%20This%20code%20is%20contributed%20by%20Aakash%20Hasija” message=”” highlight=”” provider=”manual”/]

Output:

Graph is Tree
Graph is not Tree
[ad type=”banner”]