Determine whether an undirected graph is a tree (Acyclic Connected Graph)
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.
Recommended Read:
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 <iostream> #include <vector> 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<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int n) { // resize the vector to hold `n` elements of type `vector<int>` 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<bool> &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<bool> 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<Edge> 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
|
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 110 111 112 113 114 115 116 117 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; // A class to store a graph edge class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // A class to represent a graph object class Graph { // A list of lists to represent an adjacency list List<List<Integer>> adjList = null; // Constructor Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // add edges to the undirected graph for (Edge edge: edges) { int src = edge.source; int dest = edge.dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class Main { // Perform DFS on the graph and returns true if any back-edge // is found in the graph public static boolean DFS(Graph graph, int v, boolean[] discovered, int parent) { // mark the current node as discovered discovered[v] = true; // do for every edge (v, w) for (int w: graph.adjList.get(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 public static boolean isTree(Graph graph, int n) { // to keep track of whether a vertex is discovered or not boolean[] discovered = new boolean[n]; // Perform DFS traversal from the first vertex boolean 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; } public static void main(String[] args) { // List of graph edges as per the above diagram List<Edge> edges = Arrays.asList( new Edge(0, 1), new Edge(1, 2), new Edge(2, 3), new Edge(3, 4), new Edge(4, 5), new Edge(5, 0) // edge (5, 0) introduces a cycle in the graph ); // total number of nodes in the graph (0 to 5) int n = 6; // construct graph Graph graph = new Graph(edges, n); if (isTree(graph, n)) { System.out.println("The graph is a tree"); } else { System.out.println("The graph is not a tree"); } } } |
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.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)