그래프 탐색 알고리즘: DFS, BFS

1. DFS

Depth First Search(깊이 우선 탐색)은 한 정점(node)부터 시작해서 한 방향으로 탐색을 시작해서 더 이상 탐색할 것이 없을 때 이전 노드로 돌아와서 다음으로 연결된 노드를 확인하는 탐색 방법이다.

1부터 탐색을 시작했을 때 각 노드들이 탐색되는 순서를 표기

DFS를 구현하는 방법에는 재귀와 스택을 이용한 방법이 있다.

//visited[] = 해당 노드를 방문했는지 저장하는 배열 (모든 원소가 false로 초기화됨)
//edges[][] = 각 노드별로 연결된 노드들을 저장한 배열

//스택을 이용한 DFS
function dfs(index){  
    let stacks = [];
    stacks.push(index);
    visited[index] = true;
    while(stacks.length){
        const next = stacks.pop();
        edges[next].forEach((elem) => {
            if(!visited[elem]){
                stacks.push(elem);
                visited[elem] = true;
            }
        });
        console.log(next);
    }
}

//재귀호출을 이용한 DFS
function dfs_recursive(index){  
   visited[index] = true;
   console.log(index);
   edges[index].forEach((elem) => {
       if(!visited[elem]){
           dfs_recursive(elem)
       }
   });   
}

2. BFS

Breadth First Search(너비우선탐색)은 한 정점(node)과 연결된 모든 노드들을 먼저 탐색하는 방법이다.

1부터 탐색을 시작했을 때 각 노드들이 탐색되는 순서를 표기

BFS는 큐를 이용해서 구현할 수 있다.

//visited[] = 해당 노드를 방문했는지 저장하는 배열 (모든 원소가 false로 초기화됨)
//edges[][] = 각 노드별로 연결된 노드들을 저장한 배열

function bfs(index){
    let queue = [];
    queue.push(index);
    visited[index] = 1;
    while(queue.length){
        const next = queue.shift();
        edges[next].forEach((elem) => {
            if(!visited[elem]){
                queue.push(elem);
                visited[elem] = true;
            }
        });
        console.log(next);
    }
}