[그래프 탐색] BFS와 DFS, 위상정렬

DFS

---

DFS는 한 노드에서 시작하여 가능한 다음 분기로 넘어가기 전에 해당 분기를 모두 탐색하는 방법이다.

이로인해 DFS는 주로 재귀를 통해 구현된다.

주로 모든 노드를 탐색해야하는 경우 이 방법을 사용한다.

구현은 간단하나, 속도는 너비 우선 탐색에 비해 느리다.

DFS 구현시 중요한 부분은 어떤 노드를 방문했었는지 여부를 검사하는 것이다.

이를 검사하지 않는다면 무한 루프에 빠질 가능성이 있다.

백트래킹

해가 될 수 없다고 판단되면, 왔던 길을 되돌아가 다른 길을 찾아가는 방식

트리 탐색에서 불필요한 부분을 버리고 탐색을 최적화하기에 '트리 가지치기'라고 도 한다.

 

BFS

---

BFS(Breadth-First Search)는 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.

BFS는 주로 큐를 통해 구현된다.

주로 두 노드 사이의 최단경로를 구하는데 사용된다.

BFS와 마찬가지로 무한루프에 빠지지 않도록 어떤 노드를 방문했었는지 여부를 검사하는 것이 중요하다.

 

 

위상정렬(Topological Sort)

---

위상정렬은 방향 그래프에서 정점의 방향을 거스르지 않고 한쪽으로 나열하는 것을 말한다.

위상정렬은 비순환 방향 그래프에 대해서만 적용 가능하다.

 

 

위상정렬은 선후관계가 중요한 작업들을 순차적으로 처리해야하는 문제에서 사용될 수 있다.

예를들면, 대학 선수과목 신청이나 프로그램 빌드 상황이다.

A2 과목을 듣기 위해서는 A1 과목을 들었는지,

A 모듈을 구동하기 위해 A가 의존하는 B 모듈이 빌드되어있는지와 같은 상황에 적용될 수 있다.

 

비순환 방향 그래프(DAG: Directed Acyclic Graph)

사이클이 없는 방향 그래프

위상정렬 원리

---

• In-degree(진입 차수) : 정점으로 들어오는 간선의 개수
• Out-degree(진출 차수) : 정점에서 나가는 간선의 개수

위상 정렬은 진입차수가 0인 정점을 시작으로 그 정점에서 나가는 간선들을 제거한다.

그 후, 다시 진입차수가 0을 정점을 배치하는 과정을 반복한다.

위상정렬은 스택이나 큐를 통해 구현될 수 있다.

 

[예시]

<1회전>

노드	0	1	2	3	4	5
진입차수	1	2	2	0	1	1

 

스택 or 큐 : 3

 

<2회전>

노드	0	1	2	3	4	5
진입차수	0	2	2	0	0	1

 

스택 or 큐 : 0, 4

 

<3회전>

노드	0	1	2	3	4	5
진입차수	0	0	1	0	0	1

 

스택 or 큐 : 1

 

<4회전>

노드	0	1	2	3	4	5
진입차수	0	0	0	0	0	1

 

스택 or 큐 : 2

 

<5회전>

노드	0	1	2	3	4	5
진입차수	0	0	0	0	0	0

 

스택 or 큐 : 5