Given a directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.

The following graph contains a cycle 0—1—3—0, so it’s not DAG. If we remove edge 3–0 from it, it will become a DAG.

Recommended Read:

We can use Depth–first search (DFS) to solve this problem. The idea is to find if any back-edge is present in the graph or not. A digraph is a DAG if there is no back-edge present in the graph. Recall that a back-edge is an edge from a vertex to one of its ancestors in the DFS tree.

Fact: For an edgeu —> v in a directed graph, an edge is a back edge if departure[u] < departure[v].

Proof: We have already discussed the relationship between all four types of edges involved in the DFS in the previous post. Following are the relationships we have seen between the departure time for different types of edges involved in a DFS of a directed graph:

Back edge (u, v):

departure[u] < departure[v]

Forward edge (u, v): departure[u] > departure[v]

Cross edge (u, v): departure[u] > departure[v]

Note that for tree edge, forward edge and cross edge, departure[u] > departure[v]. But only for the back edge, the relationship departure[u] < departure[v] holds true. So, it is guaranteed that an edge (u, v) is a back-edge, not some other edge if departure[u] < departure[v].

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

110

111

112

113

114

115

#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 directed graph

for (auto &edge: edges) {

adjList[edge.src].push_back(edge.dest);

}

}

};

// Perform DFS on the graph and set the departure time of all vertices of the graph

int DFS(Graph const &graph, int v, vector<bool>

&discovered, vector<int> &departure, int &time)

{

// mark the current node as discovered

discovered[v] = true;

// do for every edge (v, u)

for (int u: graph.adjList[v])

{

// if `u` is not yet discovered

if (!discovered[u]) {

DFS(graph, u, discovered, departure, time);

}

}

// ready to backtrack

// set departure time of vertex `v`

departure[v] = time++;

}

// Returns true if given directed graph is DAG

bool isDAG(Graph const &graph, int n)

{

// keep track of whether a vertex is discovered or not

vector<bool> discovered(n);

// keep track of the departure time of a vertex in DFS

vector<int> departure(n);

int time = 0;

// Perform DFS traversal from all undiscovered vertices

// to visit all connected components of a graph

for (int i = 0; i < n; i++)

{

if (!discovered[i]) {

DFS(graph, i, discovered, departure, time);

}

}

// check if the given directed graph is DAG or not

for (int u = 0; u < n; u++)

{

// check if (u, v) forms a back-edge.

for (int v: graph.adjList[u])

{

// If the departure time of vertex `v` is greater than equal

// to the departure time of `u`, they form a back edge.

// Note that departure[u] will be equal to

// departure[v] only if `u = v`, i.e., vertex

// contain an edge to itself

if (departure[u] <= departure[v]) {

return false;

}

}

}

// no back edges

return true;

}

int main()

{

// vector of graph edges as per the above diagram

vector<Edge> edges = {

{0, 1}, {0, 3}, {1, 2}, {1, 3}, {3, 2}, {3, 4}, {3, 0}, {5, 6}, {6, 3}

};

// total number of nodes in the graph (labelled from 0 to 6)

int n = 7;

// build a graph from the given edges

Graph graph(edges, n);

// check if the given directed graph is DAG or not

if (isDAG(graph, n)) {

cout << “The graph is a DAG”;

}

else {

cout << “The graph is not a DAG”;

}

return 0;

}

Output:
The graph is not a DAG

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

118

119

120

121

122

123

124

125

126

127

128

129

130

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 directed graph

for (Edge edge: edges) {

adjList.get(edge.source).add(edge.dest);

}

}

}

class Main

{

// Perform DFS on the graph and set the departure time of all

// vertices of the graph

private static int DFS(Graph graph, int v, boolean[] discovered,

int[] departure, int time)

{

// mark the current node as discovered

discovered[v] = true;

// do for every edge (v, u)

for (int u: graph.adjList.get(v))

{

// if `u` is not yet discovered

if (!discovered[u]) {

time = DFS(graph, u, discovered, departure, time);

}

}

// ready to backtrack

// set departure time of vertex `v`

departure[v] = time++;

return time;

}

// Returns true if given directed graph is DAG

public static boolean isDAG(Graph graph, int n)

{

// keep track of whether a vertex is discovered or not

boolean[] discovered = new boolean[n];

// keep track of the departure time of a vertex in DFS

int[] departure = new int[n];

int time = 0;

// Perform DFS traversal from all undiscovered vertices

// to visit all connected components of a graph

for (int i = 0; i < n; i++)

{

if (!discovered[i]) {

time = DFS(graph, i, discovered, departure, time);

}

}

// check if the given directed graph is DAG or not

for (int u = 0; u < n; u++)

{

// check if (u, v) forms a back-edge.

for (int v: graph.adjList.get(u))

{

// If the departure time of vertex `v` is greater than equal

// to the departure time of `u`, they form a back edge.

// Note that departure[u] will be equal to

// departure[v] only if `u = v`, i.e., vertex

// contain an edge to itself

if (departure[u] <= departure[v]) {

return false;

}

}

}

// no back edges

return true;

}

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(0, 3), new Edge(1, 2),

new Edge(1, 3), new Edge(3, 2), new Edge(3, 4),

new Edge(3, 0), new Edge(5, 6), new Edge(6, 3)

);

// total number of nodes in the graph (labelled from 0 to 6)

int n = 7;

// build a graph from the given edges

Graph graph = new Graph(edges, n);

// check if the given directed graph is DAG or not

if (isDAG(graph, n)) {

System.out.println(“The graph is a DAG”);

}

else {

System.out.println(“The graph is not a DAG”);

}

}

}

Output:
The graph is not a DAG

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

76

77

78

79

80

81

82

83

84

85

# 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 directed graph

for (src, dest) in edges:

self.adjList[src].append(dest)

# Perform DFS on the graph and set the departure time of all vertices of the graph

def DFS(graph, v, discovered, departure, time):

# mark the current node as discovered

discovered[v] = True

# do for every edge (v, u)

for u in graph.adjList[v]:

# if `u` is not yet discovered

if not discovered[u]:

time = DFS(graph, u, discovered, departure, time)

# ready to backtrack

# set departure time of vertex `v`

departure[v] = time

time = time + 1

return time

# Returns true if the given directed graph is DAG

def isDAG(graph, n):

# keep track of whether a vertex is discovered or not

discovered = [False] * n

# keep track of the departure time of a vertex in DFS

departure = [None] * n

time = 0

# Perform DFS traversal from all undiscovered vertices

# to visit all connected components of a graph

for i in range(n):

if not discovered[i]:

time = DFS(graph, i, discovered, departure, time)

# check if the given directed graph is DAG or not

for u in range(n):

# check if (u, v) forms a back-edge.

for v in graph.adjList[u]:

# If the departure time of vertex `v` is greater than equal

# to the departure time of `u`, they form a back edge.

# Note that `departure[u]` will be equal to `departure[v]`

# only if `u = v`, i.e., vertex contain an edge to itself

if departure[u] <= departure[v]:

return False

# no back edges

return True

if __name__ == ‘__main__’:

# List of graph edges as per the above diagram

edges = [(0, 1), (0, 3), (1, 2), (1, 3), (3, 2), (3, 4), (3, 0), (5, 6), (6, 3)]

# total number of nodes in the graph (labelled from 0 to 6)

n = 7

# build a graph from the given edges

graph = Graph(edges, n)

# check if the given directed graph is DAG or not

if isDAG(graph, n):

print(‘The graph is a DAG’)

else:

print(‘The graph is not a DAG’)

Output:
The graph is not a DAG

The time complexity of the above solutions 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: Check if a digraph is a DAG (Directed Acyclic Graph) or not. Info created by GBee English Center selection and synthesis along with other related topics.