Welcome to this comprehensive guide on detecting cycles in directed graphs using Kahn's algorithm! This lesson is designed for beginners and intermediate learners, and we'll cover the concept from the ground up. By the end of this lesson, you'll not only understand how Kahn's algorithm works but also be able to apply it in real-world projects. š
A graph is a collection of objects (vertices or nodes) and the relationships between those objects (edges or links). In a graph, the connections between vertices are represented as unidirectional (directed) or bidirectional (undirected) lines.
A directed graph, also known as a digraph, is a graph where edges have a specified direction. This means that the edges connect vertices in a specific way, and the connection between two vertices is considered distinct from the connection in the opposite direction.
A cyclic graph is a graph that contains a cycle, which is a path that starts and ends at the same vertex. In a cyclic graph, it's possible to traverse from one vertex to another and then return to the starting vertex by following the edges.
Kahn's algorithm is a topological sorting algorithm used to detect cycles in directed graphs. The algorithm sorts the vertices of a graph in such a way that for every edge (u, v), vertex u comes before vertex v in the sorted order. This sorting ensures that no vertex with outgoing edges can be placed after its dependent vertices.
def indegree(vertices, edges):
# Initialize indegree dictionary
indegree = {vertice: 0 for vertice in vertices}
# Calculate indegrees for each vertex
for edge in edges:
indegree[edge[1]] += 1
return indegree
def topological_sort(vertices, edges, indegree):
sorted_vertices = []
# Process vertices with 0 indegree
while len(indegree) > 0:
for vertice in indegree:
if indegree[vertice] == 0:
sorted_vertices.append(vertice)
for edge in edges:
if edge[0] == vertice:
indegree[edge[1]] -= 1
indegree = {vertice: indegree[vertice] for vertice in indegree if indegree[vertice] > 0}
return sorted_vertices
def detect_cycle(vertices, edges):
indegree = indegree(vertices, edges)
sorted_vertices = topological_sort(vertices, edges, indegree)
# Check if all vertices have been processed
for vertice in vertices:
if vertice not in sorted_vertices:
return True
return False
# Example usage
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('D', 'F')]
print(detect_cycle(vertices, edges)) # Output: Trueimport java.util.*;
public class Graph {
private List<List<Integer>> adjacencyList;
private int[] indegrees;
public Graph(int vertices) {
this.adjacencyList = new ArrayList<>();
this.indegrees = new int[vertices];
for (int i = 0; i < vertices; i++) {
this.adjacencyList.add(new ArrayList<>());
}
}
public void addEdge(int vertex1, int vertex2) {
this.adjacencyList.get(vertex1).add(vertex2);
this.indegrees[vertex2]++;
}
public List<Integer> topologicalSort() {
List<Integer> sortedVertices = new ArrayList<>();
Queue<Integer> zeroIndegreeQueue = new LinkedList<>();
for (int i = 0; i < this.indegrees.length; i++) {
if (this.indegrees[i] == 0) {
zeroIndegreeQueue.add(i);
}
}
while (!zeroIndegreeQueue.isEmpty()) {
int currentVertex = zeroIndegreeQueue.poll();
sortedVertices.add(currentVertex);
for (int neighbor : this.adjacencyList.get(currentVertex)) {
this.indegrees[neighbor]--;
if (this.indegrees[neighbor] == 0) {
zeroIndegreeQueue.add(neighbor);
}
}
}
if (sortedVertices.size() != this.indegrees.length) {
return Collections.emptyList();
}
return sortedVertices;
}
public boolean hasCycle() {
List<Integer> sortedVertices = this.topologicalSort();
if (sortedVertices.size() != this.indegrees.length) {
return true;
}
for (int vertex : this.indegrees) {
if (vertex > 0) {
return true;
}
}
return false;
}
// Example usage
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 2);
graph.addEdge(4, 3);
System.out.println(graph.hasCycle()); // Output: true
}What is a cyclic graph?
That's it for today! We've learned about detecting cycles in directed graphs using Kahn's algorithm. With practice, you'll become more comfortable with this concept and be able to apply it in your own projects. Happy coding! ā