In an undirected graph, a cycle is a path that starts and ends at the same vertex, and consists of at least one other vertex that is visited more than once. To detect cycles in an undirected graph, one approach is to use the Depth-First Search (DFS) algorithm.
The DFS algorithm starts at a vertex and explores as far as possible along each branch before backtracking. During the exploration, it keeps track of which vertices have already been visited, and for each visited vertex, it also keeps track of the vertex that it was visited from (i.e., its parent).
To detect cycles, we can modify the DFS algorithm as follows: for each vertex v that is visited, we check all of its neighbors u. If u has already been visited, and u is not v’s parent, then there is a cycle in the graph.
This is because if u has already been visited, then it is reachable from v by a path. And if u is not v’s parent, then the path from v to u includes at least two edges, which means that there is a cycle.
Overall, the time complexity of detecting cycles in an undirected graph using DFS is O(V+E), where V is the number of vertices and E is the number of edges in the graph.
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)
adjList.computeIfAbsent(v) { mutableListOf() }.add(u)
}
fun isCyclicUtil(v: Int, visited: BooleanArray, parent: Int): Boolean {
visited[v] = true
for (u in adjList[v]!!) {
if (!visited[u]) {
if (isCyclicUtil(u, visited, v)) {
return true
}
} else if (u != parent) {
return true
}
}
return false
}
fun isCyclic(): Boolean {
val visited = BooleanArray(numVertices) { false }
for (v in 0 until numVertices) {
if (!visited[v]) {
if (isCyclicUtil(v, visited, -1)) {
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, 3)
// 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 does not contain a cycle”, since the graph is a simple path without any cycles.
In this implementation, the class Graph represents an undirected graph with a constructor that takes the number of vertices as an argument. The function addEdge() adds an undirected edge between vertices u and 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 the parent vertex parent of v. 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 an undirected 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.