Detecting Cycles in Graphs: DFS and Disjoint Set Approaches
Detecting cycles in a graph is an essential task in computer science. The presence of cycles can inform or deter specific operations. For instance, in dependency resolution, cycles can cause deadlocks. This article will explore two prevalent methods to detect cycles in both directed and undirected graphs: Depth First Search (DFS) and the Disjoint Set.
Why Detecting Cycles is Crucial
- Dependency Resolution: Systems, like package managers, need to know dependencies between items. A cycle can indicate a deadlock.
- Networking: In computer networks, routing loops can lead to data packets circulating indefinitely.
- Database Systems: To ensure consistent reads, database systems must avoid read cycles.
1. DFS for Detecting Cycles
DFS can be used for detecting cycles as it explores as far as possible along each branch before backtracking.
Directed Graph:
For directed graphs, a cycle is present if a vertex is revisited.
function hasCycleDFS(graph, node, visited, stack) {
visited[node] = true;
stack[node] = true;
for(let adj of graph[node]) {
if(!visited[adj]) {
if(hasCycleDFS(graph, adj, visited, stack)) {
return true;
}
} else if(stack[adj]) {
return true;
}
}
stack[node] = false;
return false;
}
Undirected Graph:
For undirected graphs, if an adjacent vertex is visited and is not the parent, then there is a cycle.
function hasCycleDFSUndirected(graph, node, visited, parent) {
visited[node] = true;
for(let adj of graph[node]) {
if(!visited[adj]) {
if(hasCycleDFSUndirected(graph, adj, visited, node)) {
return true;
}
} else if(adj !== parent) {
return true;
}
}
return false;
}
2. Disjoint Set for Detecting Cycles
A Disjoint Set (Union-Find) can efficiently detect a cycle in undirected graphs. The principal idea is: for every edge, make subsets using both the vertices. If both vertices are in the same subset, a cycle is present.
function find(parent, i) {
if(parent[i] === -1) return i;
return find(parent, parent[i]);
}
function union(parent, x, y) {
let xSet = find(parent, x);
let ySet = find(parent, y);
if(xSet !== ySet) {
parent[xSet] = ySet;
}
}
function hasCycle(graph) {
let parent = Array(graph.vertices).fill(-1);
for(let edge of graph.edges) {
let x = find(parent, edge.src);
let y = find(parent, edge.dest);
if(x === y) return true;
union(parent, x, y);
}
return false;
}
Conclusion
Detecting cycles in graphs is fundamental for many algorithms and applications. Both the DFS and Disjoint Set methods offer efficient means to do this, with each having its use-cases. It’s important to choose the method best suited to the type of graph and the specific application in question.