그래프 탐색 알고리즘
그래프 탐색 알고리즘은 DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 두가지 종류로 나눌 수 있다.
두가지 알고리즘에 대해 알아보고 해당 알고리즘을 javascript 언어로 구현해보도록 하겠다.
DFS란?
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 특정한 경로로 쭉 타고 밑바닥까지 내려간 후, 막다른 길에 도착하면 다시 돌아와 다른 경로로 탐색
- Stack 자료구조 사용 (FILO 방식)
- 가장 깊은 노드까지 도달했을 때 탐색한 경로를 역추적하여 되돌아나오기 위해 스택 사용
- 이미 방문한 노드를 다시 방문하지 않기 위해 방문한 노드를 따로 저장 (방문처리)
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 그래프 탐색의 경우 어떤 노드를 방문했었는지의 여부를 반드시 검사해야 함
그림 설명
- 시작 정점을 1로 설정
- 1번 탐색시작. 1번과 연결되어있고 방문 안한 정점을 찾음 (=2번) 2번으로 이동함.
- 2번 탐색시작. 2번과 연결되어있고 방문 안한 정점을 찾음 (=3번) 3번으로 이동함.
- 3번 탐색시작. 3번과 연결되어있고 방문 안한 정점을 찾음 (=4번) 4번으로 이동함.
- 4번 탐색시작. 4번과 연결되어있는 방문 안한 정점을 찾음 (=존재하지않음) 다시 3번으로 올라감.
- 3번 탐색시작. 3번과 연결되어있고 방문 안한 정점을 찾음 (=존재하지않음) 2번으로 올라감.
- 2번 탐색시작. 2번과 연결되어있고 방문 안한 정점을 찾음 (=존재하지않음) 1번으로 올라감.
- 1번 탐색시작. 1번과 연결되어있고 방문 안한 정점을 찾음 (=5번) 5번으로 이동함.
해당 과정을 방문 안한 곳이 없을때 까지 반복한다.
JavaScript로 구현하기
JavaScript에서 DFS의 원리
- 큐에 시작 정점을 넣는다.
- 큐에서 가장 오래 있던 것을 뽑아낸다. 그와 관련된 것을 큐에 넣는다. (앞 쪽에 넣음)
- 큐의 앞에 있는 정점을 뽑아내면서 위와 같은 과정을 반복한다.
- 큐가 빌 때까지 반복한다.
- 1번으로 시작. 1번에서 갈 수 있는 곳을 (=2, 5, 9) 큐에 넣는다.
Queue : 2, 5, 9- 큐에 가장 먼저 있는 것을 뽑음. (=2) 2를 뽑아내고 2번에서 갈 수 있는 곳을 (=3) 큐에 넣는다.
Queue : 3, 5, 9- 큐에 가장 먼저 있는 것을 뽑음. (=3) 3을 뽑아내고 3번에서 갈 수 있는 곳을 (=4) 큐에 넣는다.
Queue : 4, 5, 9- 위 과정을 큐가 빌 때 까지 반복한다.
위와같은 방법으로 Stack을 활용해서 재귀함수를 쓰지 않고 구현이 가능하다.
그래프 생성
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'G', 'H', 'I'],
D: ['B', 'E', 'F'],
E: ['D'],
F: ['D'],
G: ['C'],
H: ['C'],
I: ['C', 'J'],
J: ['I']
};DFS 구현 함수
// graph 자료구조와 startNode를 입력
const DFS = (graph, startNode) => {
const visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...graph[node], ...needVisit];
}
}
return visited;
};BFS란?
- 가까운 노드부터 탐색하는 알고리즘
- 가까운 노드들을 우선적으로 방문하고 멀리있는 노드를 나중에 방문
- 큐 자료구조를 사용
- 현재 노드의 이웃 노드를 큐에 집어넣어 자연스럽게 먼저 들어간 노드를 먼저 탐색 (FIFO)하게 되는 방식
그림설명
- 처음에 1번으로 시작한다. 큐에 1을 넣는다.
Queue : 1- 큐에 가장 앞에 있는 것을 뽑는다. (=1) 1번과 연결되어있는 정점을 (=2, 3, 4) 큐에 넣는다.
Queue : 2, 3, 4- 큐에 가장 앞에 있는 것을 뽑는다. (=2) 2번과 연결되어있는 정점을 (=5) 큐에 넣는다.
Queue : 3, 4, 5- 큐에 가장 앞에 있는 것을 뽑는다. (=3) 3번과 연결되어있는 정점을 (=6, 7) 큐에 넣는다.
Queue : 4, 5, 6, 7
해당 과정을 방문 안한 곳이 없을때 까지 반복한다.
JavaScript로 구현하기
JavaScript에서 BFS의 원리
- 탐색 스택, 방문 배열을 생성
- 탐색을 시작하는 정점을 탐색스택에 쌓는다.
- 탐색스택이 없어질때까지 아래과정을 반복한다.
1) 스택 최상단에 있는 것을 없애고, 이를 탐색한다.
2) 탐색 시에 방문 했는지 체크, 했다면 패스
3) 방문 안했다면, 이를 방문 배열에 넣고 그 정점과 이어진 정점들을 배열에 다시 쌓는다.
Stack을 활용하여 재귀함수를 쓰지않고 구현이 가능하다.
BFS 구현 함수
// graph 자료구조와 startNode를 입력
const BFS = (graph, startNode) => {
let visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
if (!visited.includes(node)) { // 해당 노드 방문이 처음이라면,
visited.push(node);
needVisit = [...needVisit, ...graph[node]];
}
}
return visited;
};DFS vs BFS
DFS 장점
- 코드가 직관적이고 구현하기 쉽다.
DFS 단점
- 깊이가 깊어지면, 메모리 비용을 예측하기 어렵다.
- 최단 경로를 알 수 없다
적용
- 경로의 특징을 저장해야 하는 경우
- 길 찾기
- 미로 문제
BFS 장점
- 비교적 효율적인 운영 가능, 시간/공간 복잡도 면에서 안정적이다.
- 최단 경로를 구할 수 있다.
BFS 단점
- 구현이 비교적 까다롭다.
- 모든 지점을 탐색하는 경우에는 큐에 메모리가 어느정도 준비되어 있어야 한다.
적용
- 길 찾기, 라우팅
- 웹 크롤러
- 소셜 네트워크에서 멀리 떨어진 사람 찾기
- 그래프에서 주변 위치 찾기
결론
DFS? BFS?
BFS는 기본적인 메모리가 필요하지만, 가지고 있는 메모리를 효율적으로 관리할 수 있고, DFS는 전체적으로 적게 들지만 예상치 못한 값을 만나게 되면 메모리가 터질 수 있다.
DFS는 경로의 특징을 구할 때, BFS는 최단거리를 구할 때 ,,
FrontEnd Developer.