How do you detect a cycle in a directed graph?

Explanation: :

Detecting a cycle in a directed graph is a common problem in computer science, especially relevant in scenarios like dependency resolution, task scheduling, and deadlock detection. In a directed graph, a cycle is a path that starts and ends at the same vertex. To detect a cycle, we can use algorithms like Depth First Search (DFS) with a recursion stack or Kahn’s algorithm using topological sorting.

• DFS Approach: Utilize a recursion stack to track nodes along the current path. If you revisit a node on this stack, a cycle is detected.
• Kahn’s Algorithm: Use a topological sorting approach by removing nodes with zero in-degrees iteratively. If there are nodes left in the end, they form a cycle.

Key Talking Points:

• Directed Graph: A graph where edges have direction.
• Cycle Detection: Identifying if there’s a path that starts and ends at the same node.
• DFS with Recursion Stack:
  • Use a visited array to track visited nodes.
  • Use a recursion stack to track nodes in the current path.
• Kahn’s Algorithm:
  • Count in-degrees of each vertex.
  • Use a queue to track nodes with zero in-degrees.
  • Detect leftover nodes for cycles.

NOTES:

Reference Table:

Pseudocode:

Here's a pseudocode for detecting a cycle using DFS:

function isCyclic(graph):
    visited = set()
    recursionStack = set()

    function dfs(v):
        if v not in visited:
            visited.add(v)
            recursionStack.add(v)
            
            for neighbor in graph[v]:
                if neighbor not in visited and dfs(neighbor):
                    return True
                elif neighbor in recursionStack:
                    return True

        recursionStack.remove(v)
        return False

    for node in graph:
        if dfs(node):
            return True
    return False

Follow-Up Questions and Answers:

1. How would you modify the algorithm to work on an undirected graph?

   • Answer: For an undirected graph, while using DFS, ensure that you do not revisit the immediate parent node of the current node. This approach helps in distinguishing between a cycle and a back edge to a parent.

2. What are some real-world applications of cycle detection in directed graphs?

   • Answer: Cycle detection is crucial in areas such as:
     • Dependency resolution: Ensures no circular dependencies exist in package managers.
     • Deadlock detection: Identifying tasks or processes that are waiting on each other to complete.
     • Scheduling: Ensuring there are no cyclical dependencies between tasks in project management.

3. Can you detect a cycle in a graph with negative weights?

   • Answer: Yes, cycles can be detected in graphs with negative weights using similar algorithms. However, for detecting negative weight cycles specifically, the Bellman-Ford algorithm is more appropriate because it’s designed to handle graphs with weighted edges.