Detecting Cycles in a Directed Graph

Cycle detection is a fundamental problem in graph theory with applications in various areas like deadlock detection in operating systems, dependency resolution, and identifying circular references in data structures. This challenge asks you to implement a function that determines whether a given directed graph contains a cycle. Understanding cycle detection is crucial for ensuring the correctness and stability of many algorithms and systems.

Problem Description

You are given a directed graph represented as an adjacency list. The adjacency list is a dictionary where keys are nodes and values are lists of nodes that the key node points to. Your task is to write a function has_cycle(graph) that takes this adjacency list as input and returns True if the graph contains a cycle, and False otherwise.

The algorithm should efficiently traverse the graph to identify cycles. You should consider using Depth-First Search (DFS) to achieve this. The DFS should track visited and currently visiting nodes to accurately detect cycles.

Key Requirements:

• The function must accept a dictionary representing the adjacency list as input.
• The function must return a boolean value: True if a cycle exists, False otherwise.
• The algorithm should handle disconnected graphs correctly (i.e., a cycle might exist in one component but not another).
• The algorithm should be efficient in terms of time complexity.

Expected Behavior:

The function should correctly identify cycles in various graph structures, including:

• Graphs with no cycles.
• Graphs with a single cycle.
• Graphs with multiple cycles.
• Disconnected graphs with cycles in some components.
• Graphs with self-loops (a node pointing to itself).

Edge Cases to Consider:

• Empty graph (no nodes or edges).
• Graph with a single node and no edges.
• Graph with a single node and a self-loop.
• Graphs with multiple components.

Examples

Example 1:

Input: graph = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['A']
}
Output: True
Explanation: The graph contains a cycle: A -> B -> C -> A.

Example 2:

Input: graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
Output: False
Explanation: The graph has no cycles.

Example 3:

Input: graph = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A'],
    'D': ['E'],
    'E': []
}
Output: True
Explanation: The graph has two components. The first component (A -> B -> C -> A) has a cycle, while the second component (D -> E) does not.

Example 4:

Input: graph = {
    'A': ['A']
}
Output: True
Explanation: The graph contains a self-loop, which is a cycle.

Constraints

• The graph can contain up to 1000 nodes.
• Each node is represented by a string.
• The adjacency list will only contain valid nodes as keys and lists of strings as values.
• The time complexity of your solution should be O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.

Notes

Consider using Depth-First Search (DFS) to traverse the graph. Maintain three states for each node during the DFS:

1. Unvisited: The node has not been visited yet.
2. Visiting: The node is currently being visited in the current DFS path.
3. Visited: The node has been completely visited and all its descendants have been explored.

A cycle is detected when you encounter a "Visiting" node during the DFS. Remember to handle disconnected graphs by iterating through all nodes and starting a DFS from each unvisited node.