Algorithm

• Initialize: Start from an arbitrary vertex, mark it as visited, and add it to the result list.
• Explore: For each unvisited neighbor of the current vertex, recursively call DFS.
• Backtrack: If all neighbors have been visited, backtrack to the previous vertex.

Detecting Cycles

• Visited Set: As DFS explores the graph, it marks each visited node by adding it to the visited set.
• Exploring Set: While traversing from one vertex to another, DFS keeps track of the nodes currently being explored in the current path.
• Back Edge Detection: If during traversal, DFS encounters a neighbor that is already in the exploring set, it indicates the presence of a cycle in the graph.

Python

def dfs(graph, start, visited=None, result=None):
    if visited is None:
        visited = set()
    if result is None:
        result = []

    visited.add(start)
    result.append(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)

    return result

DFS Cycle Detection For Directed Graph

def dfs_cycle_detection_for_directed_graphs(n, graph):
    def dfs(node):
        visited[node] = True
        recursion_stack[node] = True

        for neighbor in graph[node]:
            if visited[neighbor] == False:
                if dfs(neighbor):
                    return True
            elif recursion_stack[neighbor] == True:
                return True

        recursion_stack[node] = False
        return False

    visited = [False] * n
    recursion_stack = [False] * n
    for node in range(n):
        if visited[node] == False:
            if dfs(node):
                return True
    return False

Where V is vertices and E is edges

$Time = O(V + E)$