DFS: 깊이 우선 탐색- iteration, recursion

Chapter 7 DFS

DFS - Depth first search

function dfsRecursion(adjacencyList: Array<Array<number>>, here: number, visited: boolean[]) {
    visited[here] = true;
    const currentEdges = adjacencyList[here];
    for (let i = 0; i < currentEdges.length; i++) {
        const connectedVertex = currentEdges[i];
        if (visited[connectedVertex] === true) continue;
        dfsRecursion(adjacencyList, connectedVertex, visited);
    }
}

function dfsIteration(adjacencyList: Array<Array<number>>, here: number, visited: boolean[]) {
    const q: number[] = [here];
    while (q.length > 0) {
        const currentVertex = q.shift() as number;
        if (visited[currentVertex] === true) continue;

        const currentEdges: number[] = adjacencyList[currentVertex];
        visited[currentVertex] = true;
        q.unshift(...currentEdges);

        console.log('dfs::iteration:: ', { here, currentVertex, currentEdges, q });
    }
}

function dfsAll(adjacencyList: number[][]) {

      // recursion
    visited = new Array(adjacencyList.length).fill(false);
    for (let i = 0; i < adjacencyList.length; i++) {
        if (visited[i] === true) continue;
        dfsRecursion(adjacencyList, i, visited);
    }

    // ineration
    visited = new Array(adjacencyList.length).fill(false);
    for (let i = 0; i < adjacencyList.length; i++) {
        if (visited[i] === true) continue;
        dfsIteration(adjacencyList, i, visited);
    }
}

let visited: boolean[] = [];
let adjacencyList: number[][] = [
    [],
    [2, 10],
    [1, 3, 4, 6, 8],
    [2, 4, 5, 6],
    [2, 3],
    [3],
    [2, 3, 7],
    [6],
    [2, 9],
    [8],
    [1, 8],
];

dfsAll(adjacencyList);