深さ優先探索（DFS）

// 再帰による深さ優先探索
function dfsRecursive(graph, startNode, visited = new Set()) {
    // 現在のノードを訪問
    visited.add(startNode);
    console.log(`訪問: ${startNode}`);
    
    // 隣接ノードを再帰的に探索
    const neighbors = graph[startNode] || [];
    for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

// スタックによる反復実装
function dfsIterative(graph, startNode) {
    const visited = new Set();
    const stack = [startNode];
    
    while (stack.length > 0) {
        const currentNode = stack.pop();
        
        if (!visited.has(currentNode)) {
            visited.add(currentNode);
            console.log(`訪問: ${currentNode}`);
            
            // 隣接ノードをスタックに追加（逆順で追加）
            const neighbors = graph[currentNode] || [];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                if (!visited.has(neighbors[i])) {
                    stack.push(neighbors[i]);
                }
            }
        }
    }
}

// 使用例
const graph = {
    A: ['B', 'C'],
    B: ['D', 'E'],
    C: ['F'],
    D: [],
    E: ['F'],
    F: []
};

console.log("=== 再帰実装 ===");
dfsRecursive(graph, 'A');

console.log("=== 反復実装 ===");
dfsIterative(graph, 'A');

// パス探索版（目標ノードまでの経路を発見）
function findPath(graph, start, target, visited = new Set(), path = []) {
    visited.add(start);
    path.push(start);
    
    if (start === target) {
        return path; // 経路を発見
    }
    
    const neighbors = graph[start] || [];
    for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
            const result = findPath(graph, neighbor, target, visited, [...path]);
            if (result) {
                return result;
            }
        }
    }
    
    return null; // 経路が見つからない
}

// 連結成分の検出
function getConnectedComponents(graph) {
    const visited = new Set();
    const components = [];
    
    for (const node in graph) {
        if (!visited.has(node)) {
            const component = [];
            dfsComponent(graph, node, visited, component);
            components.push(component);
        }
    }
    
    return components;
}

function dfsComponent(graph, node, visited, component) {
    visited.add(node);
    component.push(node);
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
            dfsComponent(graph, neighbor, visited, component);
        }
    }
}