그래프 탐색(Graph Traversals)

하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 과정

1. BFS(Breadth Frist Search): 너비 우선 탐색
2. DFS(Depth Frist Search): 깊이 우선 탐색

그래프(Graph)

정점(node)과 간선(edge)으로 이루어진 데이터 구조

두 정점 사이의 관계를 나타냄

• 지도 상의 최단 경로 찾기 등의 문제를 해결하는데 사용

그래프의 구성 요소

1. 무방향 그래프(Undirected Graph)
   • 간선에 방향이 없는 그래프
   • 두 정점이 양방향으로 연결
2. 방향 그래프(Directed Graph)
   • 간선에 방향이 있는 그래프
   • 정점 간의 관계가 일방적일 수 있음
     • 각 간선은 한쪽 방향으로만 이동할 수 있음

그래프의 표현 방법

1. 인접 행렬(Adjacency Matrix)
   • 2차원 배열(행렬)을 사용해 그래프를 표현
   • 행렬의 행과 열은 그래프의 정점에 해당하며 값은 간선의 존재 여부를 나타냄
   • 장점
     • 구현이 쉽고 두 정점 사이의 간선 유무를 $O(1)$에 확인할 수 있음
   • 단점
     • 기억장소의 낭비가 많고 노드의 개수보다 간선이 많은 경우 비효율적

# 인접 행렬 표현

graph = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]
]

1. 인접 리스트(Adjancency List)
   • 각 정점마다 연결된 정점들의 리스트를 저장하는 방법
   • 장점
     • 메모리 효율적이며 큰 그래프를 효과적으로 표현할 수 있음
   • 단점
     • 간선의 존재 여부를 확인하는 데 $O(n)$이 걸림(n: 정점의 수)

# 인접 리스트 표현

graph = {
    0: [1],
    1: [0, 2, 3],
    2: [1],
    3: [1]
}

---

BFS(Breadth First Search)

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

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• 큐(Queue)를 사용하여 구현

BFS의 동작 원리

1. 시작 정점 선택: 탐색을 시작할 정점을 선택
2. 정점 방문: 시작 정점을 방문하고 그 정점에 연결된 모든 입점 정점을 큐에 넣음
3. 큐에서 정점 제거: 큐의 맨 앞에 있는 정점을 꺼내고 그 정점과 인접한 정점들을 탐색
4. 탐색 반복: 큐가 빌 때까지 과정을 반복하며 모든 정점을 탐색

BFS의 특징

• 최단 경로 탐색에 적합: 시작 정점에서 각 정점까지의 최단 경로를 찾을 수 있음
• 레벨 순서 탐색: 시작 정점에서 가까운 정점부터 차례대로 방문하므로 탐색 순서가 레벨 순서로 이루어짐
• 큐(Queue)를 사용: 정점을 큐에 넣고 탐색할 때 큐에서 꺼내므로 FIFO 방식으로 동작

---

DFS(Depth First Search)

시작 정점에서 한 방향으로 계속해서 깊이 탐색을 진행한 후 더 이상 갈 곳이 없으면 이전으로 돌아가는 방식으로 탐색

• 스택(Stack) 또는 재귀 호출 을 사용하여 구현

DFS의 동작 원리

1. 시작 정점 선택: 탐색을 시작할 정점 선택
2. 정점 방문: 현재 정점을 방문하고 그 정점에 인접한 첫 번째 정점으로 이동
3. 깊이 탐색: 더 이상 방문할 정점이 없을 때까지 계속해서 깊이 탐색을 진행
4. 되돌아가기: 방문할 정점이 없으면 이전 정점으로 돌아가서 다른 경로로 탐색 계속

DFS의 특징

• 재귀적 탐색: DFS는 재귀적으로 동작하여 한 경로를 끝까지 탐색
• 스택 사용: DFS는 스택을 사용하거나 재귀 호출로 구현
• 경로 찾기: 모든 경로를 탐색해야 할 때 유용하며 순환 구조를 가진 그래프의 탐색에도 적합

---

BFS와 DFS의 차이점

탐색 방식	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
자료구조	큐(Queue)	스택(Stack) 또는 재귀 호출
탐색 순서	시작 정점에서 가까운 정점부터 탐색	한 방향으로 끝까지 탐색
특징	최단 경로 탐색에 적합	경로를 모두 탐색할 때 적합
시간 복잡도	O(V + E)	O(V + E)

V: 그래프의 정점(vertex)

E: 그래프의 간선(edge)

• 그래프의 모든 정점을 방문하고 각 정점에서 나오는 모든 간선을 한 번씩 탐색
  • 그래프의 크기에 따라 탐색 시간이 증가할 수 있음

---

DFS와 BFS가 필요한 이유

1. 그래프의 모든 정점 방문

   • 인접 리스트나 행렬은 정점들이 어떻게 연결되어 있는지를 보여주지만, 정점을 하나씩 순차적으로 방문하는 과정을 처리하지는 않음
   • 그래프의 모든 정점을 방문하거나 특정 경로를 찾을 때 필수적

2. 연결된 모든 정점 탐색
   그래프에서 어떤 정점이 다른 정점들과 연결되어 있는지, 또는 특정 경로가 존재하는지를 파악하려면 단순히 인접 리스트나 행렬을 확인하는 것만으로는 부족

   DFS나 BFS를 사용해야 연결된 모든 경로를 따라가며 정점을 탐색할 수 있다.

3. 경로 탐색 및 최단 경로 찾기

4. 복잡한 그래프 구조 탐색