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

그래프 탐색 알고리즘: 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]){ solution(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); } }

from http://jjakddo-studio.tistory.com/9 by ccl(A) rewrite - 2021-11-25 23:00:51