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 vertexv 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:

Table of Contents

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.

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.