Undirected Graph:
Directed Graph:
BFS (Un-directed graph)
- Initialize: Start by marking the source node (src) as visited and enqueue it.
- BFS Traversal:
- While the queue is not empty, dequeue a node.
- For each neighbor of the dequeued node:
- If the neighbor is unvisited, mark it as visited and enqueue it.
- If the neighbor is already visited, a cycle is detected, so return true.
- No Cycle: If the queue is exhausted without detecting a cycle, return false.
Breadth-First Search (BFS) explores nodes level by level. If a neighbor is encountered that has already been visited and is not the direct parent in the BFS tree, it indicates the presence of a back edge, which forms a cycle.
public class Main{
static class Edge{
int src;
int nbr;
Edge(int src,int nbr){
this.nbr=nbr;
this.src=src;
}
}
static class Pair{
int v;
String psf;
Pair(int v, String psf){
this.v = v;
this.psf = psf;
}
}
public static boolean isCyclicBFS(ArrayList<Edge>[] graph, boolean[] visited, int src) {
ArrayDeque<Pair> q = new ArrayDeque<>();
q.add(new Pair(src, src + ""));
visited[src] = true; // mark the source node as visited
while (q.size() > 0) {
Pair rem = q.removeFirst(); // remove
int currV = rem.v;
// work - No work
// add*
for (Edge e : graph[currV]) {
if (!visited[e.nbr]) {
q.add(new Pair(e.nbr, rem.psf + e.nbr));
visited[e.nbr] = true; // mark the neighbor node as visited
} else {
return true; // cycle detected
}
}
}
return false;
}
}DFS(Un-directed graph)
- Initialize: Create a visited array to track visited nodes and a parent array to track the parent node of each visited node during the DFS traversal.
- DFS Traversal:
- For each unvisited node, start a DFS traversal:
- Mark the current node as visited.
- For each neighbor of the current node:
- If the neighbor is unvisited, set its parent as the current node and recursively perform DFS.
- If the neighbor is already visited and it is not the parent of the current node, a cycle is detected.
- For each unvisited node, start a DFS traversal:
- No Cycle: If no cycle is detected after traversing all nodes, return false.
Depth-First Search (DFS) explores nodes along a path as far as possible before backtracking. By keeping track of the parent node for each visited node, the algorithm can detect back edges (edges that point to an ancestor in the DFS tree), which indicate the presence of a cycle.
public class Main{
static class Edge{
int src;
int nbr;
Edge(int src,int nbr){
this.nbr=nbr;
this.src=src;
}
}
static class Pair{
int v;
String psf;
Pair(int v, String psf){
this.v = v;
this.psf = psf;
}
}
public static boolean isCyclicDFS(ArrayList<Edge>[] graph, int v){
boolean[] visited = new boolean[v];
//simple "int parent = -1" se bhi kaam ho jayega. We can update parent for each src node during traversal.
int[] parent = new int[v];
Arrays.fill(parent, -1);
for(int i = 0; i < v; i++){
if(!visited[i]){
if(dfs(graph, visited, i, parent)){
return true;
}
}
}
return false;
}
public boolean dfs(ArrayList<Edge>[] graph, boolean[] visited, int src, int[] parent){
visited[src] = true;
for(Edge e: graph[src]){
if(!visited[e.nbr]){
parent[e.nbr] = src;
if(dfs(graph, visited, e.nbr, parent)){
return true;
}
} else{
//if "int parent = -1" liya hota toh this condition would've been: (parent != e.nbr)
if(parent[src] != e.nbr){
return true;
}
}
}
return false;
}
}Here’s an example to illustrate the difference:
Suppose we start the DFS traversal from node 1. When we reach node 3, its neighbor node 1 is already visited. However, node 1 is the parent of node 3 (parent[3] = 1), so it is not considered a cycle. The condition parent[src] != e.nbr (i.e., 1 != 1) will be false, and the DFS traversal will continue.
On the other hand, if there was an additional edge connecting nodes 4 and 5, forming a cycle, the else part would detect it. When node 5 is visited, its neighbor node 4 is already visited, but node 4 is not the parent of node 5 (parent[5] != 4). In this case, the condition parent[src] != e.nbr will be true, indicating the presence of a cycle, and the method will return true.
DFS(directed graph)
-
TheÂ
visited array keeps track of the nodes that have been visited during the entire DFS traversal. -
TheÂ
dfsVisited array keeps track of the nodes that have been visited in the current DFS call stack. -
Initialize:
- Create a visited array to keep track of all nodes that have been visited.
- Create a dfsVisited array to track nodes visited in the current DFS path.
-
DFS Traversal:
- For each unvisited node, start a DFS traversal:
- Mark the current node as visited in both visited and dfsVisited.
- For each neighbor of the current node:
- If the neighbor is unvisited, recursively perform DFS.
- If the neighbor is visited and also in the dfsVisited path, a cycle is detected.
- After exploring all neighbors, reset the dfsVisited status for the current node (backtrack).
-
No Cycle: If no cycle is detected after traversing all nodes, return false.
- DFS Traversal: This DFS-based approach effectively detects cycles by tracking the current path (dfsVisited). If a node is revisited within the same path, it indicates a cycle.
- Backtracking: By resetting dfsVisited[src] to false after exploring all neighbors, the algorithm ensures that the path is correctly managed, allowing the detection of cycles in other parts of the graph.
public static boolean isCyclicDFS(ArrayList<Edge>[] graph, int v){
boolean[] visited = new boolean[v];
boolean[] dfsVisited = new boolean[v];
for(int i = 0; i < v; i++){
if(!visited[i]){
if(dfs(graph, i, visited, dfsVisited)){
return true;
}
}
}
return false;
}
public static boolean dfs(ArrayList<Edge>[] graph, int src, boolean[] visited, boolean[] dfsVisited){
visited[src] = true;
dfsVisited[src] = true;
for(Edge e: graph[src]){
if(!visited[e.nbr]){
if(dfs(graph, e.nbr, visited, dfsVisited)){
return true;
}
} else if(dfsVisited[e.nbr]){
return true;
}
}
// no cycle found, reset the dfsVisited for next call from another source node.
dfsVisited[src] = false;
return false;
}BFS(directed graph)
- Refer to Topological Sort