Detecting cycles in directed graphs is a bit more complicated than in undirected graphs because there are two types of edges – forward and backward – that need to be considered. One way to detect cycles in a directed graph is to use depth-first search (DFS) and maintain a stack of visited vertices.
To detect a cycle, we start a DFS from each unvisited vertex, marking each vertex as visited and pushing it onto the stack. As we traverse the graph, we look for back edges – edges that connect a vertex to one of its ancestors in the stack. If we encounter a back edge, it means that there is a cycle in the graph, and we can return true.
If we complete the DFS traversal without finding a cycle, we can backtrack and pop the vertices off the stack. We mark each vertex as visited during the backtrack so that we don’t visit it again during a future DFS traversal.
This algorithm has a time complexity of O(V+E), where V is the number of vertices and E is the number of edges in the graph.
Here’s an implementation of cycle detection in a directed graph using DFS in Kotlin:
class Graph(private val numVertices: Int) {
private val adjList: MutableMap<Int, MutableList<Int>> = mutableMapOf()
fun addEdge(u: Int, v: Int) {
adjList.computeIfAbsent(u) { mutableListOf() }.add(v)
}
fun isCyclicUtil(v: Int, visited: BooleanArray, stack: BooleanArray): Boolean {
visited[v] = true
stack[v] = true
for (u in adjList[v]!!) {
if (!visited[u]) {
if (isCyclicUtil(u, visited, stack)) {
return true
}
} else if (stack[u]) {
return true
}
}
stack[v] = false
return false
}
fun isCyclic(): Boolean {
val visited = BooleanArray(numVertices) { false }
val stack = BooleanArray(numVertices) { false }
for (v in 0 until numVertices) {
if (!visited[v]) {
if (isCyclicUtil(v, visited, stack)) {
return true
}
}
}
return false
}
}
fun main() {
// Create a graph with 4 vertices
val g = Graph(4)
// Add edges to the graph
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 0)
// Check if the graph contains a cycle
if (g.isCyclic()) {
println("Graph contains a cycle")
} else {
println("Graph does not contain a cycle")
}
}In the above example, the output will be “Graph contains a cycle”, since the graph contains a cycle between vertices 0, 1, and 2.
In this implementation, the class Graph represents a directed graph with a constructor that takes the number of vertices as an argument. The function addEdge() adds a directed edge from vertex u to vertex v to the graph.
The function isCyclicUtil() is a recursive helper function that takes a vertex v, an array visited that keeps track of visited vertices, and an array stack that keeps track of the vertices currently in the DFS stack. It returns true if the graph contains a cycle and false otherwise.
The function isCyclic() checks if the graph contains a cycle by iterating over all vertices of the graph and calling isCyclicUtil() on each unvisited vertex. If isCyclicUtil() returns true for any vertex, then the graph contains a cycle and the function returns true. Otherwise, the function returns false.
This implementation uses depth-first search (DFS) to detect cycles in a directed graph and has a time complexity of O(V+E), where V is the number of vertices and E is the number of edges in the graph.