dfs-cycle-test.js

/**
 * Problem: Detect Cycle in a Directed Graph
 *
 * You are given a directed graph represented as an adjacency list.
 * Each key is a node, and its value is an array of neighbors.
 *
 * Goal:
 * Return true if the graph contains a **cycle**, false otherwise.
 *
 * Example:
 * Input:
 * {
 *   A: ['B'],
 *   B: ['C'],
 *   C: ['A']
 * }
 * Output: true (cycle: A → B → C → A)
 *
 * Approach:
 * Use DFS with two sets:
 * - `visited`: tracks nodes fully explored
 * - `inStack`: tracks the current recursion stack
 * If we revisit a node that's in the stack, we've found a cycle.
 */
function hasCycle(graph) {
    const visited = new Set();
    const inStack = new Set();

    for (const node in graph) {
        if (dfs(node, graph, visited, inStack)) return true;
    }

    return false;
}

function dfs(node, graph, visited, inStack) {
    // 1. If node is in visited set, return false (already fully processed)
    // 2. If node is in inStack, return true (cycle detected)
    // 3. Add node to inStack
    // 4. Recurse on all neighbors
    // 5. After all neighbors, remove from inStack and mark visited
    // 6. Return false (no cycle from this path)
}
function testHasCycle() {
    const graph = {
        A: ['B'],
        B: ['C'],
        C: ['A'] // cycle A → B → C → A
    };

    const expected = true;
    const actual = hasCycle(graph);

    console.log(actual === expected ? "✅ PASS" : `❌ FAIL (got ${actual}, expected ${expected})`);
}

testHasCycle();