© Parineeth M R
Question 60. Find if a directed graph has a cycle
Suppose we are given an undirected graph and asked to find a cycle in it, then all we need to do is the following
1. Initialize all nodes in the graph as unvisited.
2. Pick a node that has not been visited and recursively traverse its neighbors and their neighbors and so on using depth first search. Once we traverse a node, we will mark it as visited.
3. Repeat step 2 until all the nodes in the graph are visited.
While traversing the graph, if we encounter a node that has already been visited, then there is a cycle in the undirected graph.
We can’t apply the same procedure for a directed graph. Consider the diagram below
Suppose we start from node 0 and apply DFS. We first traverse the edge from node 0 to node 1. Then from node 1 we reach node 2. So nodes 0, 1 and 2 have been visited. Then we traverse the edge from 0 to 2. But node 2 has already been visited. Since we encounter a node that we have already visited, we conclude that there is a cycle in the directed graph. However this is incorrect since there is no directed cycle in this directed graph. If we had an edge from node 2 to node 0 instead of an edge from node 0 to node 2, then the graph has a directed cycle in it.
To overcome this problem, instead of just maintaining two states whether the node has been visited or not, we maintain 3 states that are identified using colors
– White: the node has not yet been processed
– Gray: the node is currently being processed. This means that the node’s neighbors and their neighbors and so on are still being expanded
– Black: the node has been completely processed. This means that all the nodes that are reachable from this node have been traversed
During depth first search, if we encounter a node whose color is already gray, then it means that there is a cycle in the directed graph.
Using this approach, let us traverse the above directed graph. Initially all nodes are white. When we start with node 0, we change the color of 0 to gray. From 0 we move to 1. So node 1 now becomes gray. From 1 we reach 2. The color of 2 becomes gray. From 2 we try to traverse further. But there are no nodes reachable from 2. So we have finished processing node 2 and change its color to black. Then we check if we can reach another node from node 1. There are no new nodes that we can reach from node 1. So we change color of 1 to black and come back to node 0. From node 0 we can reach node 2. The color of node 2 is black. If color of 2 was still grey, then it means that there is a loop in the graph. In this case, since color of 2 is black, there is no loop in the graph.
To simplify the implementation, the nodes in the graph will be represented by integers. For each node in the graph, we will be storing its neighboring nodes as shown in the table below:
C/C++
/* Helper function that performs depth first search on the graph
cur_node: the current node that we are searching
adjacency_table: an array of vectors. If there is an edge from node 0 to
node 5, then adjacency_table[0] is a vector which stores 5 in it
color: this array indicates the color assigned to the nodes
num_nodes: total number of nodes in the graph
Return value: true if cycle exists in directed graph, false otherwise
*/
bool dfs(int cur_node, vector<int> adjacency_table[], int color[], int num_nodes)
{
bool does_cycle_exist = false;
unsigned int j;
vector<int>& neighbors = adjacency_table[cur_node];
/*Assign the gray color to the node indicating that we have
started processing this node*/
color[cur_node] = GRAY;
for (j = 0; j < neighbors.size(); ++j) {
int cur_neighbor = neighbors[j];
/*If we find a neighboring node with the gray color, then we
have found a loop*/
if (color[cur_neighbor] == GRAY) {
return true;
}
/*If the neighboring node has a white color, then perform
DFS on it*/
if (color[cur_neighbor] == WHITE) {
does_cycle_exist = dfs(cur_neighbor, adjacency_table,
color, num_nodes);
if (does_cycle_exist)
return true;
}
}
/*Assign the node the black color to indicate that we have finished
processing it*/
color[cur_node] = BLACK;
return false;
}
/* Main function that checks if cycle is present or not
adjacency_table: an array of vectors. If there is an edge from node 0
to node 5, then adjacency_table[0] is a vector which stores 5 in it
num_nodes: total number of nodes in the graph
Return value: true if cycle is present in directed graph, false otherwise
*/
bool is_cycle_present(vector<int> adjacency_table[], int num_nodes)
{
int *color = new int[num_nodes];
int i;
bool does_cycle_exist = false;
/*Assign the white color to all the nodes to indicate that we have
not started processing the nodes*/
for (i = 0; i < num_nodes; ++i)
color[i] = WHITE;
/*Go through all the nodes in the graph and perform DFS on the nodes
whose color is white*/
for (i = 0; i < num_nodes; ++i) {
if (color[i] == WHITE) {
does_cycle_exist = dfs(i, adjacency_table, color,
num_nodes);
if (does_cycle_exist)
break;
}
}
delete [] color;
return does_cycle_exist;
}
Java
/*Helper function that performs depth first search on the graph
curNode: the current node that we are searching
adjacencyTable: an ArrayList of ArrayLists. If there is an edge between node 0
and node 5, then adjacencyTable[0] is an ArrayList which stores 5 in it.
color: this array indicates color assigned to the nodes
numNodes: total number of nodes in the graph
Return value: true if cycle exists in directed graph, false otherwise
*/
public static boolean dfs(int curNode,
ArrayList<ArrayList<Integer>> adjacencyTable,
int[] color, int numNodes) {
boolean doesCycleExist = false;
ArrayList<Integer> neighbors = adjacencyTable.get(curNode);
/*Assign the gray color to the node indicating that we have
started processing this node*/
color[curNode] = GRAY;
for (int j = 0; j < neighbors.size(); ++j) {
int curNeighbor = neighbors.get(j);
/*If we find a neighboring node with the gray color, then we
have found a loop*/
if (color[curNeighbor] == GRAY) {
return true;
}
/*If the neighboring node has a white color, then perform
DFS on it*/
if (color[curNeighbor] == WHITE) {
doesCycleExist = dfs(curNeighbor, adjacencyTable,
color, numNodes);
if (doesCycleExist)
return true;
}
}
/*Assign the node the black color to indicate that we have
finished processing it*/
color[curNode] = BLACK;
return false;
}
/* Main function that checks if cycle is present or not
adjacencyTable: an ArrayList of ArrayLists. If there is an edge between node 0
and node 5, then adjacencyTable[0] is an ArrayList which stores 5 in it.
numNodes: total number of nodes in the graph
Return value: true if cycle is present in directed graph, false otherwise
*/
public static boolean isCyclePresent(
ArrayList<ArrayList<Integer>> adjacencyTable,
int numNodes) {
int[] color = new int[numNodes];
boolean doesCycleExist = false;
/*Assign the white color to all the nodes to indicate that we have not
started processing the nodes*/
int i;
for (i = 0; i < numNodes; ++i)
color[i] = WHITE;
/*Go through all the nodes in the graph and perform DFS on the
nodes whose color is white*/
for (i = 0; i < numNodes; ++i) {
if (color[i] == WHITE) {
doesCycleExist = dfs(i, adjacencyTable,
color, numNodes);
if (doesCycleExist)
break;
}
}
return doesCycleExist;
}
Python
#Helper function that performs depth first search on the graph #cur_node: the current node that we are searching #adjacency_table: a list of lists. If there is an edge between node 0 and # node 5, then adjacency_table[0] is a list which stores 5 in it. #color: this list indicates color assigned to the node #num_nodes: total number of nodes in the graph #Return value: True if cycle is present in directed graph, False otherwise def dfs(cur_node, adjacency_table, color, num_nodes) : does_cycle_exist = False neighbors = adjacency_table[cur_node] #Assign the gray color to the node indicating that we have started #processing this node color[cur_node] = GRAY for j in range(0, len(neighbors)): cur_neighbor = neighbors[j] #If we find a neighboring node with the gray color, then we #have found a loop if (color[cur_neighbor] == GRAY) : return True #If the neighboring node has a white color, then perform #DFS on it if (color[cur_neighbor] == WHITE) : does_cycle_exist = dfs(cur_neighbor, adjacency_table, color, num_nodes) if (does_cycle_exist): return True #Assign the node the black color to indicate that we have finished #processing it color[cur_node] = BLACK return False #Main function that checks if cycle is present or not #adjacency_table: a list of lists. If there is an edge between node 0 and # node 5, then adjacency_table[0] is a list which stores 5 in it. #num_nodes: total number of nodes in the graph #Return value: True if cycle is present in directed graph, False otherwise def is_cycle_present(adjacency_table, num_nodes) : does_cycle_exist = False #Assign the white color to all the nodes to indicate that we have not #started processing the nodes color = [WHITE] * num_nodes #Go through all the nodes in the graph and perform DFS on the #nodes whose color is white for i in range(0, num_nodes): if (color[i] == WHITE) : does_cycle_exist = dfs(i, adjacency_table, color, num_nodes) if (does_cycle_exist) : break return does_cycle_exist
