Given an undirected graph, check if it is a tree or not. In other words, check if a given undirected graph is an Acyclic Connected Graph or not.

For example, the graph shown on the right is a tree, and the graph on the left is not a tree as it contains a cycle `0—1—2—3—4—5—0`.

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. We can easily determine the acyclic connected graph by doing a DFS traversal on the graph. When we do a DFS from any vertex`v` in an undirected graph, we may encounter a back-edge that points to one of the ancestors of the current vertex `v` in the DFS tree. Each “back edge” defines a cycle in an undirected graph. If the back edge is `x —> y`, then since `y` is the ancestor of node `x`, we have a path from `y` to `x`. So, we can say that the path `y ~~ x ~ y` forms a cycle. (Here, `~~` represents one more edge in the path, and `~` represents a direct edge) and is not a tree.

The algorithm can be implemented as follows in C++, Java, and Python:

## C++

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 #include #include using namespace std; // Data structure to store a graph edge struct Edge { int src, dest; }; // A class to represent a graph object class Graph { public: // a vector of vectors to represent an adjacency list vector> adjList; // Graph Constructor Graph(vector const &edges, int n) { // resize the vector to hold `n` elements of type `vector` adjList.resize(n); // add edges to the undirected graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Perform DFS on the graph and returns true if any back-edge // is found in the graph bool DFS(Graph const &graph, int v, vector &discovered, int parent) { // mark the current node as discovered discovered[v] = true; // do for every edge (v, w) for (int w: graph.adjList[v]) { // if `w` is not discovered if (!discovered[w]) { if (!DFS(graph, w, discovered, v)) { return false; } } // if `w` is discovered, and `w` is not a parent else if (w != parent) { // we found a back-edge (cycle) return false; } } // no back-edges were found in the graph return true; } // Check if the given undirected graph is a tree bool isTree(Graph const &graph, int n) { // to keep track of whether a vertex is discovered or not vector discovered(n); // boolean flag to store if the graph is tree or not bool isTree = true; // Perform DFS traversal from the first vertex isTree = DFS(graph, 0, discovered, -1); for (int i = 0; isTree && i < n; i++) { // any undiscovered vertex means the graph is disconnected if (!discovered[i]) { isTree = false; } } return isTree; } int main() { // initialize edges as per the above diagram vector edges = { {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 0} // edge (5, 0) introduces a cycle in the graph }; // total number of nodes in the graph (0 to 5) int n = 6; // build a graph from the given edges Graph graph(edges, n); if (isTree(graph, n)) { cout << “The graph is a tree”; } else { cout << “The graph is not a tree”; } return 0; }

Output:
The graph is not a tree

## Java

Output:
The graph is not a tree

## Python

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 # A class to represent a graph object class Graph: # Constructor def __init__(self, edges, n): # A list of lists to represent an adjacency list self.adjList = [[] for _ in range(n)] # add edges to the undirected graph for (src, dest) in edges: self.adjList[src].append(dest) self.adjList[dest].append(src) # Perform DFS on the graph and returns true if any back-edge # is found in the graph def DFS(graph, v, discovered, parent): # mark the current node as discovered discovered[v] = True # do for every edge (v, w) for w in graph.adjList[v]: # if `w` is not discovered if not discovered[w]: if not DFS(graph, w, discovered, v): return False # if `w` is discovered, and `w` is not a parent elif w != parent: # we found a back-edge (cycle) return False # no back-edges were found in the graph return True # Check if the given undirected graph is a tree def isTree(graph, n): # to keep track of whether a vertex is discovered or not discovered = [False] * n # flag to store if the graph is tree or not isTree = True # Perform DFS traversal from the first vertex isTree = DFS(graph, 0, discovered, -1) for i in range(n): # any undiscovered vertex means the graph is disconnected if not discovered[i]: return False return isTree if __name__ == ‘__main__’: # List of graph edges as per the above diagram. # Note edge (5, 0) introduces a cycle in the graph edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)] # total number of nodes in the graph (0 to 5) n = 6 # construct graph graph = Graph(edges, n) if isTree(graph, n): print(‘The graph is a tree’) else: print(‘The graph is not a tree’)

Output:
The graph is not a tree

The time complexity of the above solution is O(V + E), where `V` and `E` are the total number of vertices and edges in the graph, respectively.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?

You are watching: Determine whether an undirected graph is a tree (Acyclic Connected Graph). Info created by GBee English Center selection and synthesis along with other related topics.