저번시간에는 그래프 자료구조를 C언어로 구현하는 작업을 해보았다.
이번시간에는 DFS와 BFS에 대해서 알아볼 예정이다.
DFS와 BFS는 무엇인가?
DFS(Depth First Search)는 깊이 우선 탐색이다. 아래 자료와 같이 한방향으로 갈 수 있을 때 까지 깊게 들어간 다음 가장 가까운 갈림길로 돌아와(백트래킹) 다시 깊게 들어가는 탐색 방식이다(재귀적으로 동작한다). 돌아오기 위해서는 스택이 필요하다. 스택을 활용해서 구현이 가능하다. 그림으로 간단하게 표현하자면 아래와 같이 나타낼 수 있다.
BFS(Breath First Search)는 너비 우선 탐색이다. 아래 자료와 같이 한 정점에서 가장 가까운 정점들을 방문하고 나중에 떨어진 정점들을 방문하는 탐색 방식이다. 큐를 사용해서 구현이 가능하다. 그림으로 간단하게 표현하자면 아래와 같이 나타낼 수 있다.
DFS 동작방식
먼저 , DFS에 관해 자세히 알아보도록 하자.
DFS는 다음과 같은 알고리즘으로 작동한다.
1. 탐색을 시작할 정점 V를 방문처리 및 스택에 추가
2. V의 인접 정점 중 방문처리가 되지 않은 정점이 발견될 경우 그 정점을 방문처리 및 스택에 추가 및 그 정점에 대해 DFS를 다시 시작
3. 만약 정점 V에 대해 인접정점이 모두 방문처리가 되었을 경우 V를 스택에서 제거해준다.
4. (2)~(3)의 과정을 반복
5. 스택이 빌 경우 종료.
이를 조금 더쉽게 재귀적으로 나타내면
DFS(V):
if(정점 V 가 방문되지 않은 경우)
정점 V에 대해 방문처리;
for all u ∈ (정점 V의 인접 정점들)
DFS(u);
으로 나타낼 수 있다.
글만으로는 이해하기 어려울 수 있으니 다음 예제를 통해 살펴보도록 하자.
다음과 같은 그래프가 있다고 가정해보자. 이때, 탐색의 시작 정점은 A라고 가정하자.
이 그래프의 인접리스트는 다음과 같다.
[a]: [b] [c]
[b]: [d] [e]
[c]: [f] [g]
[d]: [b]
[e]: [b]
[f]: [c]
[g]: [c]
먼저, A부터 탐색을 시작하므로, A를 방문처리를 해주고 A를 스택에 추가해준다.
A의 인접 정점들을 탐색하면서, 방문처리 되지 않은 B를 방문 처리후 스택에 추가해준다.
그리고 B에서 DFS를 수행해준다.
B의 인접정점들을 차례로 탐색하는데, 이때 D가 방문되지 않았으므로 방문처리 후 스택에 추가한다.
D로 이동해 D에서부터 DFS를 시작한다.
D의 인접정점들을 차례로 탐색하는데
D와 연결된 정점 중에 방문되지 않은 정점이 없다. D를 스택에서 꺼냄으로써 상위 정점으로 이동한다.
즉, B로 이동해 탐색을 재개한다.
B의 인접정점들을 차례로 탐색하는데,
이때 E가 방문되지 않았으므로 방문처리 후 스택에 추가한다.
E로 이동해 E에서부터 DFS를 시작한다.
E의 인접정점들을 차례로 탐색하는데
E와 연결된 정점 중에 방문되지 않은 정점이 없다. E를 스택에서 꺼냄으로써 상위 정점으로 이동한다.
즉, B로 이동해 탐색을 재개한다.
B의 인접정점들을 차례로 탐색하는데
B와 연결된 정점 중에 방문되지 않은 정점이 없다. B를 스택에서 꺼냄으로써 상위 정점으로 이동한다.
즉, A로 이동해 탐색을 재개한다.
A의 인접정점들을 차례로 탐색하는데,
이때 C가 방문되지 않았으므로 방문처리 후 스택에 추가한다.
C로 이동해 C에서부터 DFS를 시작한다.
C의 인접정점들을 차례로 탐색하는데,
이때 F가 방문되지 않았으므로 방문처리 후 스택에 추가한다.
F로 이동해 F에서부터 DFS를 시작한다.
F의 인접정점들을 차례로 탐색하는데
F와 연결된 정점 중에 방문되지 않은 정점이 없다. F를 스택에서 꺼냄으로써 상위 정점으로 이동한다.
즉, C로 이동해 탐색을 재개한다.
C의 인접정점들을 차례로 탐색하는데,
이때 G가 방문되지 않았으므로 방문처리 후 스택에 추가한다.
G로 이동해 G에서부터 DFS를 시작한다.
G의 인접정점들을 차례로 탐색하는데
G와 연결된 정점 중에 방문되지 않은 정점이 없다. G를 스택에서 꺼냄으로써 상위 정점으로 이동한다.
즉, C로 이동해 탐색을 재개한다.
C의 인접정점들을 차례로 탐색하는데
C와 연결된 정점 중에 방문되지 않은 정점이 없다. C를 스택에서 꺼냄으로써 상위 정점으로 이동한다.
즉, A로 이동해 탐색을 재개한다.
A의 인접정점들을 차례로 탐색하는데
A와 연결된 정점 중에 방문되지 않은 정점이 없다. A를 스택에서 꺼낸다.
스택이 모두 비었으며 이는 곧 A의 상위 정점은
없다는 의미이며 탐색이 종료가 된다.
BFS 알아보기
BFS에 대해 자세히 알아보도록하자.
BFS는 다음과 같은 알고리즘으로 동작한다.
글만으로는 이해하기 어려울 수 있으니 다음 예제를 통해 살펴보도록 하자.
BFS가 인접리스트 방식으로 나타낸 그래프에서 작동하는 방식을 알아보자. 아래와 같은 그래프가 있다고 가정하자.
탐색을 시작하는 정점은 A라고 가정하자.
A부터 탐색을 시작한다. A의 방문처리 후 A를 큐에 추가한다.
A를 큐에서 제거한다.
A의 인접 정점들 중 방문되지않은 정점들을 모두 방문처리 해주고 큐에 넣는다.
B를 큐에서 제거하며
B의 방문되지 않은 정점들을 모두 방문처리 해주고 큐에 넣는다.
C를 큐에서 제거하며
C의 방문되지 않은 정점들을 모두 방문처리 해주고 큐에 넣는다.
D를 큐에서 제거하며
D의 방문되지 않은 정점들을
모두 방문처리 해주고 큐에 넣는다.
다만, 이때는 방문되지 않은 정점이 없다.
E를 큐에서 제거하며
E의 방문되지 않은 정점들을
모두 방문처리 해주고 큐에 넣는다.
다만, 이때는 방문되지 않은 정점이 없다.
F를 큐에서 제거하며
F의 방문되지 않은 정점들을
모두 방문처리 해주고 큐에 넣는다.
다만, 이때는 방문되지 않은 정점이 없다.
G를 큐에서 제거하며
G의 방문되지 않은 정점들을
모두 방문처리 해주고 큐에 넣는다.
다만, 이때는 방문되지 않은 정점이 없다.
큐가 비었으므로 탐색을 종료한다.
이번 시간에는 DFS와 BFS가 무엇이며 어떻게 동작하는지에 관해 알아보았다. 다음시간에는 다른 그래프의 예제를 살펴보며 복습하고 이를 실제로 C로 구현해보는 시간을 가지도록 하겠다.
혹시 이해가 어렵거나 잘못된 부분이 있다면 언제든지 댓글을 달아주시면 감사하겠습니다!
'수업내용정리 > 자료구조' 카테고리의 다른 글
| [자료구조][C언어]큐(Queue)란?(1)_큐의 개념 (0) | 2023.04.11 |
|---|---|
| [자료구조][C언어]그래프란?(4)_DFS와 BFS_좀 더 알아보기 (0) | 2022.12.29 |
| [자료구조][C언어]그래프란?(2)_그래프의 구현 (0) | 2022.12.06 |
| [자료구조][C언어]그래프란?(1)_그래프의 개념 (0) | 2022.12.01 |
| [자료구조][C언어]스택이란?(5)_후위표기식 만들기 (0) | 2022.11.28 |
