Saturday, 10 January 2015

which graph is tree (Is it a tree)




For checking if the graph is a tree we need to check those 3 things.
1. There are N nodes and N-1 edges. If the number of edges is different than N-1 than the graph is not a tree for sure,
2. We need to run a DFS or BFS , from any edge we want. If we meet a node which we already visited => the graph has cycles => the graph is not a tree. (  Every time we are on some node, we calculate the number of his neighbors which we already visited, the number must be less than 2 because for the cycles we shouldn't count the node which we were in our previous step. Check the source code for clarification).
3. If the previous 2 steps proved that our graph is a tree we need to check for one more thing. A tree must have only one component, there shouldn't be any other trees apart form our graph.