순서

1. BFS

• BFS 그래프 예시
• BFS 그래프 탐색 과정
• BFS 코드

2. DFS

• DFS 그래프 예시
• DFS 그래프 탐색 과정
• DFS 코드

BFS(너비우선탐색)

• BFS의 정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• BFS의 특징

  • 깊게(deep) 탐색하기 전에 넓게(wide) 탐색함
  • 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
  • 재귀적으로 동작하지 않음
  • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야함 (그렇지 않으면 무한 루프에 빠질 위험이 있음)
  • 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용하여 선입선출의 원칙으로 탐색함

• BFS의 시간복잡도
  - 인접 리스트로 표현된 그래프: O(N+E)
  
  - 인접 행렬로 표현된 그래프: O(N^2)
  

BFS 그래프 예시

BFS 그래프 탐색 과정

1. 정점 0을 시작 정점으로 BFS (큐에 0 추가)
   

2. 큐에서 0을 꺼내고 0에 방문 후 0과 인접한 정점들을 큐에 추가
   

3. 큐에 1 추가
   

4. 큐에 3 추가
   

5. 큐에 4 추가
   

6. 큐에서 1을 꺼내고 1에 방문 후 1과 인접한 정점들을 큐에 추가
   

7. 0은 이미 방문했고 큐에 2를 추가
   

8. 큐에서 3을 꺼내고 3에 방문 후 3과 인접한 정점들을 큐에 추가
   

9. 0은 이미 방문했고 2와 4는 이미 큐에 있으니 추가 안함
   

10. 큐에서 4를 꺼내고 4에 방문 후 4와 인접한 정점들을 큐에 추가
    

11. 0과 3은 이미 방문했고 2는 이미 큐에 있으니 추가 안함
    

12. 큐에서 2를 꺼내고 2에 방문
    

13. 더이상 추가할 정점이 없고 큐도 비었으니 탐색 종료
    

BFS 코드

DFS(깊이우선탐색)

• DFS의 정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 그래프의 깊은 노드를 우선적으로 탐색하는 방법

• DFS의 특징

  • 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함
  • 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
  • 자기 자신을 호출하는 순환 알고리즘의 형태
  • 되돌아가기 위해서는 스택 필요
  • 현재 탐색중인 노드들만 기억하기 때문에 메모리 사용이 적고, 당연한 이야기지만 찾으려는 노드가 깊을 경우에 BFS보다 빠르게 찾을 수 있음
  • 해가 없는 경로를 탐색하는 경우에도 경로가 끝날때 까지 탐색함
  • 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택

• DFS의 시간복잡도
  - 인접 리스트로 표현된 그래프: O(max(V+E))
  - 인접 행렬로 표현된 그래프: O(V^2)
  

DFS 그래프 예시

DFS 그래프 탐색 과정

DFS 코드