DFS & BFS

깊이 우선 탐색(Depth-First Search:DFS)

- 바이너리 트리를 순회할 때 사용하는 방법의 inorder, preorder, postorder를 사용

- 인접 노드를 타고 인접 노드가 없을 때까지 도달 후 다시 거슬러 올라오며 순회

 

Stack을 이용하여 구현

1. 스택에 시작 노드를 넣어준 후 방문처리(Visited) 한다.
2. 스택의 노드 하나를 꺼낸다(Pop).
3. 꺼낸 노드가 인접(Adjacent) 노드가 있으며 방문하지 않았다면,  스택에 넣어준 후(Push) 방문처리한다.
4. 스택이 비워질 때까지 2, 3번 과정을 반복한다.

 

Recursion(재귀호출)을 이용한 구현

1. 시작 노드를 먼저 방문처리 후 인접 노드를 방문한다.
2. 방문한 인접 노드를 방문처리 후 인접 노드가 있다면 차례로 방문한다.
3. 방문할 인접 노드가 없을 때까지 2번 과정을 반복 호출한다.

 

넓이 우선 탐색(Breadth-First Search:BFS)

- 인접 노드를 모두 방문 후 인접 노드의 인접 노드를 방문하며 순회

- 레벨 단위로 탐색

 

Queue를 이용하여 구현

1. 큐에 시작 노드를 넣어준 후 방문처리(Visited) 한다.
2. 큐의 노드 하나를 꺼낸다(Dequeue).
3. 꺼낸 노드가 인접 노드가 있으며 방문하지 않았다면,  큐에 넣어준 후(Enqueue) 방문처리한다.
4. 큐가 비워질 때까지 2, 3번 과정을 반복한다.

DFS&BFS 탐색순서

 

구현 스크립트

https://github.com/SangkiHong/AlgorithmPractice/tree/master/DFS

GitHub - SangkiHong/AlgorithmPractice

https://github.com/SangkiHong/AlgorithmPractice/tree/master/BFS

GitHub - SangkiHong/AlgorithmPractice