1. Depth-First-Search
최대한 깊게 내려간 뒤, 다시 내려갈 곳이 없으면 되돌아가서 다음 방향으로 이동.
루트 혹은 다른 임의노드로부터 시작하여 다른 방향으로 넘어가기 전에 해당 방향을 완벽하게 탐색하는 방식.
출처 : dfs 사진
Stack혹은재귀 함수를 통해 구현한다.
- 모든 노드를 탐색할 수 있음.
- bfs에 비해 간단함
- 속도는 느림.
작동방식
Step1
처음에는 Visited와 Stack 모두 비어있는 상태이다.
처음 노드는 0번째를 선택한다.
Step2
0을 방문했으므로 Visited 배열에 0을 Push한다. 그리고 0과 인접한 노드인 3, 2, 1를 Stack 배열에 Push한다.
Step3
그 다음 Stack의 0번째 노드인 1번노드를 방문한다.
즉, Stack에는 pop을 하고 Visited에는 1노드를 push를 한다.
1에는 인접한 노드가 0밖에 없는데 0은 이미 Visited된 노드이기 때문에 따로 Stack에 추가한다.
Step4
다음으로 Stack에서 Pop을 하면 2가 나오고 그 2를 Visited에 push한다.
2에는 인접한 노드가
3, 4가 있는데 Stack에 이미 3이 존재하기 때문에 4만 push한다.
Step5
똑같이 4 노드를 Visited에 push하고 모든 인접 노드를 스택에 push한다.
Step6
Stack에 마지막 남은 3을 pop하고 visited에 push한다.
이런식으로 DFS 순회가 진행된다.
2. BFS
Root 노드 혹은 다른 임의의 노드부터 인접한 노드를 먼저 탐색하는 방법이다.
출처 : bfs 사진
Queue를 사용해서 구현한다.
- 최소비용 문제
- 간선의 가중치가 1이다.
- 정점과 간선의 개수가 적다( 시간제약, 메모리 제한 내의 만족한다.)
작동방식
Step1
root 노드인 1을 먼저 Visited 에 push를 하고 인접 노드인 2, 5, 3을 Queue에 enqueue한다.
Step2
다음 Queue에서 dequeue하여 2번노드를 visited하고 2번노드의 인접한 노드를 Queue에 enqueue한다.
Step 3
다른과정들도 마찬가지로 진행된다.