Question

Given a directed graph G, give an algorithm that tests if G is acyclic. Analyze running time.

Answer 1

Given a graph G,with n (number of vertices) and all the edges in the graph as input.We have to check if G is acyclic or not i.e, if G contains a cycle then it is cyclic otherwise acyclic.

G is a directed graph.

it can be connected or disconnected(many connected components).

our algorithm will work in both cases.

ALGORITHM:

We will do DFS (depth first search) of the graph G and while traversing we will assign one of the 3 colors(explained below) to each vertex.

RED: if a vertex is not visited yet (or not processed yet).All vertices are initially RED.

GREEN: if a vertex is under process(or is being processed) i.e, its DFS has started and not yet completed(it's subtree is not yet processed).

BLUE: if a vertex's DFS is completed i.e, the vertex and it's subtree (descendants) is processed(or visited).

so While traversing the graph (or while doing the DFS), if we encounter an edge from current vertex to a GREEN vertex,then this edge is a BACK EDGE. Hence we can say that a cycle is detected and the graph G is cycilc or graph G is not acyclic.

BACK EDGE:

the above graph shown in the picture is also taken as an first example input of the below code.

second example input.

HERE IS CODE DESCRIBING THE ABOVE ALGORITHM IN PYTHON:

please see the code carefully , as it is in python(user friendly) it will be easily understood.

#code begins..............

from collections import defaultdict
class Graph():#class for graph
   def __init__(self,number_of_vertices):#constructor
       self.number_of_vertices = number_of_vertices
       self.graph= defaultdict(list)
      
   def add_edge(self,u,v):# from u to v as graph is directed.
       self.graph[u].append(v)#edge u-v added.
      
   def dfs(self, u, color):#color is a list containing color of each vertex.
       color[u]="GREEN"
       for v in self.graph[u]:
           if color[v] == "GREEN":
               return True
           if color[v]=="RED" and self.dfs(v,color)==True:
               return True
       color[u]="BLUE"
       return False
      
   def is_cyclic(self):#function which return true if graph has cycle and false otherwise.
   color=[]
   for i in range(0,self.number_of_vertices):#if there are disconnected components then for all components dfs() will be called.
   color.append("RED")#all vertices are initialised to RED as all are unvisited initially
   for i in range(0,self.number_of_vertices):
   if color[i]=="RED":#if a vertex is unvisited then it is processed and checked for a cycle in its subtree.
   if self.dfs(i,color)==True:
   return True
   return False
  
g1=Graph(5)#example 1 in which graph contains cycle.
g1.add_edge(0,1)
g1.add_edge(0,3)
g1.add_edge(1,2)
g1.add_edge(2,3)
g1.add_edge(2,1)
g1.add_edge(3,4)

if(g1.is_cyclic()):
print("graph g1 is not acyclic.")#this is printed in this case.
else:
print("graph g1 is acyclic.")
  
g2=Graph(7)#example 2 in which graph does not contain cycle.
g1.add_edge(0,6)
g1.add_edge(0,1)
g1.add_edge(0,2)
g1.add_edge(1,5)
g1.add_edge(2,4)
g1.add_edge(2,3)

if(g2.is_cyclic()):
print("graph g2 is not acyclic.")
else:
print("graph g2 is acyclic.")#this is printed in this case.

#code ends.

SO THIS IS THE CODE .

time complexity of above code:

as we can see , in the is_cyclic() function the for loop will execute x times where x=number of connected components in the graph,in our example it is 1.

in the dfs() function, the for loop is executed for every vertex v, e(u) times where e(u) is number of outgoing edges from u.

so time complexity is v1(for vertex v1)+e1(number of outgoing edges from it)+v2(for vertex v2)+e2(number of outgoing edges from it)+...............so on till the last vertex,

so, it is (v1+v2+v3+v4.......v times(v is number of vertices)) + (e1+e2+e3........e times(where e is total number of edges))

so finally it is O(v+e).

so the time complexity of the above algorithm is O(V+E) where V is total number of vertices and E is total number of edges.