[대학원-자료구조 4] Elementary Graph Algorithms : BFS, DFS

1. 그래프

 

자료구조 : 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위함

- 선형적 관계 : 배열, 링크드 리스트

- 계층적 관계 : 트리

- 연결관계 : 그래프

 

그래프

- 연결 데이터를 저장할 수 있는 자료 구조

- 예시 : 다양한 연결 관계(ex. 도시들 관계, 웹페이지 하이퍼링크 등)를 나타내는 데 쓰이는 유연한 구조로, 알고리즘/프로그래밍에서 입력값으로 바로 활용하기에는 추상적임

 

그래프의 표현방식 두 가지

- 그래프에서 두 노드 사이의 관계를 말할 때 adjacent(노드간에 엣지가 있음) 하다/안하다라고 얘기한다.

① 인접 행렬(adjacency matrix)

(directed graph에서의 adjacency matrix)

- from에서 to로가는 관계일 때 to의 원소에 1, 나머지는 전부 0

- adjacency를 말할때에도 to를 기준으로 말한다. 예를들어 c-d에서 '노드 d는 c에 adjacent 하다'라고 한다. (반대로 얘기하면 틀림)

 

(undirected graph에서의 adjacency matrix)

- 인접행렬에서 모든 노드는 스스로와 연결이 안 된 걸로 표시

- 어떤 노드와 어떤 노드가 연결되었는지 확인 가능 (인접행렬의 목표)

- 연결 되어있으면 1, 아니면 0 (대각선을 기준으로 symmetric)

② 인접 리스트(adjacency list)

(directed graph에서의 adjacency list)

- 1차원 배열

 

(undirected graph에서의 adjacency list)

- to에서 원소들의 순서는 상관 없음

 

2. BFS

 

그래프 탐색 : 하나의 노드를 시작점으로 해서 연결된 노드들을 모두 찾는 것을 의미

- 그래프를 탐색할 때 시작점 노드는 우리가 정하기 나름

- 그리고 이 시작점으로부터 다른 노드들을 찾아가는 것 (정보보다는 탐색이 목적)

- 그래프의 구조에 대해 의미 있는 정보들을 알아낼 수 있음

- BFS와 DFS : 각 노드를 어떤 순서로 탐색하는지에 따라 BFS, DFS로 나뉨 (본 장 주제)

 

BFS (Breadth First Search : 너비 우선 탐색)

- Breadth는 너비를 뜻하는데, BFS는 너비를 우선적으로 놓고 탐색하는 알고리즘임. 즉, 탐색 기준이 '너비'

- 추상자료형 '큐' 활용 대표 예시

추상자료형 큐 recap

예시 : 인접 리스트

- 물론 인접 리스트 뿐만아니라 행렬로도 가능

예시 : 인접 리스트

a, b, c : S로부터 동등하며 같은 너비

- {a, b, c}는 {d, e, f, g, h, i}의 어떤 것 보다 먼저 방문되어야 함

d, e, f, g, h, i : S로부터 같은 너비

 

(시험 출제 예정) BFS / DFS 관련

 

BFS 알고리즘 단계별 설명

 

 

(1) ~ (8) : 초기화 부분

- 노드들의 상태와 거리, 선행 노드 정보를 초기화한다. 탐색이 시작되기 전 모든 노드를 준비하는 과정

 

WHITE, GRAY, BLACK은 각 노드의 색깔을 나타내며 방문 상태를 의미

• WHITE: 방문하지 않음
• GRAY: 현재 탐색 중인 노드
• BLACK: 탐색 완료된 노드

(1) V[G] - {s} : 시작 노드 s를 제외한 그래프의 모든 노드를 의미

- 시작 노드만 초기화 방식이 다르기 때문에 이처럼 제외

(2) 모든 노드를 방문하지 않은 상태(WHITE)로 설정

(5) color[s] ← GRAY : 시작 노드를 GRAY로 바꾼다.

- 시작 노드가 탐색의 시작점이기 때문에 방문을 시작하면서 색을 GRAY로 변경

(8) Q ← ∅ : 큐를 초기화 : 큐는 BFS 탐색의 핵심 자료구조로, 방문할 노드들을 관리

 

(9) ~ (10) : 큐 초기화 및 시작 노드 삽입

- 큐를 초기화하고 시작 노드를 삽입한다. 탐색의 첫걸음을 준비함

 

(9) ENQUEUE(Q, s) : 큐에 시작 노드 s를 넣는다.
이때, 시작 노드는 이미 GRAY로 변경된 상태 입니다. 탐색을 시작하기 위해 가장 먼저 큐에 들어간다.

(10) while Q ≠ ∅: 큐가 비어있지 않는 한 탐색을 계속
- 큐가 비면 모든 노드가 처리되었다는 의미이므로 알고리즘이 종료

 

(11) ~ (18) : 큐를 이용한 반복 탐색

- 큐가 빌 때까지 반복하며, 현재 노드의 인접 노드를 탐색한다. 이 부분이 BFS 알고리즘의 핵심

 

(11) u ← DEQUEUE(Q) : 큐에서 가장 먼저 들어온 노드를 꺼내온다. (FIFO)
- 이 노드가 지금 탐색할 노드

(12) for each v ∈ Adj[u] : 현재 노드 u의 모든 인접 노드 v에 대해 반복

- Adj[u]는 그래프에서 노드 u와 연결된 모든 이웃 노드를 의미

(13) ~ (14) 

if color[v] = WHITE:
- 이웃 노드가 WHITE(방문되지 않은 상태)일 경우에만 탐색을 진행
- 이미 방문된 노드(즉, GRAY나 BLACK인 노드)는 다시 탐색하지 않는다.
color[v] ← GRAY :

- 해당 인접 노드 v를 방문했으므로 GRAY로 바꿉니다.

(17) ENQUEUE(Q, v):

- 방문한 인접 노드 v를 큐에 추가

- 이 노드는 나중에 탐색할 노드가 됨

(18) color[u] ← BLACK:

- 현재 노드 u의 모든 인접 노드가 처리되었으므로, 이 노드를 BLACK으로 바꾼다.

- BLACK은 탐색이 완료된 노드를 의미 → 더 이상 이 노드는 탐색할 필요가 없음

BFS 알고리즘 전체 흐름 요약

1. 초기화 단계에서 모든 노드를 WHITE로 두고 시작 노드를 큐에 넣는다.
2. 반복 탐색 루프를 통해 큐에 있는 노드를 꺼내 인접 노드를 검사
3. 방문하지 않은 노드는 GRAY로 바꾸고, 큐에 추가
4. 모든 인접 노드가 처리되면 해당 노드를 BLACK으로 처리
5. 큐가 빌 때까지 반복하며, 탐색을 종료

BFS 예시

탐색 순서 : b → {c, d, e} → {a, f}

- 너비가 같은 노드끼리는 순서 변경 가능

 

3. DFS

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

- DFS는 깊이를 우선적으로 놓고 탐색하는 알고리즘임. 즉, 탐색 기준이 '깊이'

- 추상자료형 '스택' 활용 대표 예시

추상자료형 스택 : 후입선출 (Last-in-first-out)

 

DFS 알고리즘 단계별 설명

DFS에서는 노드를 방문할 때 색깔을 바꾸어 탐색 상태를 추적 :

• WHITE: 아직 탐색하지 않음.
• GRAY: 현재 탐색 중.
• BLACK: 탐색 완료.

 

 

(1)~(3) : 노드 초기화

- 그래프 G의 모든 u에 대해서 white(미방문) 상태로 초기화

(4) 타이머 초기화

- DFS에서는 노드의 방문 및 종료 시간을 기록하는데, 이 라인은 전역변수 time을 0으로 초기화하는 부분

(5) ~ (7) : DFS 실행 루프

- 그래프의 모든 노드에 대해(5) 해당 노드가 방문되지 않았다면(6) 탐색을 시작(7)

 

 

- 이 코드는 DFS의 재귀적 탐색 과정을 구현

 

(1) ~ (3) : 방문 시 초기 작업

- 현재 방문한 노드 u 를 Gray(탐색중) 상태로 변경

(4) ~ (7) : 인접 노드 탐색(재귀 호출)

(4) 각각의 노드 u의 인접 노드 v를 탐색

(5) 인접 노드 v가 미방문 상태 white일 때에만 탐색을 시작

(7) 인접 노드 v에 대해 재귀적으로 DFS-VISIT 함수를 호출해 깊이 탐색을 이어나간다.

- 이 부분인 DFS의 깊이 우선 탐색을 구현한 핵심이며, 백트래킹은 더 이상 인접 노드가 없을 때 자동으로 이루어짐

(8) ~ (9) : 탐색 완료 처리

(8) 현재 노드 u의 탐색이 완료되었음을 나타내기 위해 BLACK으로 변경

(9) 현재 노드 u의 탐색 종료 시간을 기록 

 

DFS-VISIT 함수의 전체 흐름 정리

• 노드 방문 처리:
  • 방문한 노드를 GRAY(탐색 중) 상태로 바꾸고, 발견 시간을 기록합니다.
• 인접 노드 탐색:
  • 모든 인접 노드 중 WHITE(미방문) 상태인 노드들만 탐색합니다.
  • 재귀 호출을 통해 깊이 우선 탐색을 수행하며, 부모 노드를 기록합니다.
• 백트래킹:
  • 더 이상 인접 노드가 없으면 탐색을 종료하고, 해당 노드를 BLACK(탐색 완료) 상태로 바꿉니다.
  • 탐색이 완료된 노드의 종료 시간을 기록합니다.

4. 시간복잡도

DFS와 BFS 둘 다 시간복잡도는 O(V+E)

- V : 그래프의 Vertex(정점)의 수

- E : 그래프의 Edge(간선)의 수

- 그래프 탐색 알고리즘 중에 이보다 더 효율적인 알고리즘은 없음

---

References

- Korea University - CVO101 

- https://databridge.tistory.com/44