[자료구조][C언어]그래프란?(4)_DFS와 BFS

저번시간에는 DFS와 BFS의 개념에 관해 배웠었다.

이번시간에는 DFS와 BFS 예제를 몇가지 더 살펴볼 예정이다.

저번시간 복습을 해보자.

DFS와 BFS는 무엇인가?

DFS(Depth First Search)는 깊이 우선 탐색이다. 아래 자료와 같이 한방향으로 갈 수 있을 때 까지 깊게 들어간 다음 가장 가까운 갈림길로 돌아와 다시 깊게 들어가는 탐색 방식이다. 스택을 활용해서 구현이 가능하다.

BFS(Breath First Search)는 너비 탐색 우선이다. 아래 자료와 같이 한 정점에서 가장 가까운 정점들을 방문하고 나중에 떨어진 정점들을 방문하는 탐색 방식이다. 큐를 사용해서 구현이 가능하다.

DFS를 인접리스트 방식으로 나타낸 그래프에서 작동하는 방식을 알아보자. 아래와 같은 그래프가 있다고 가정하자.

[a]: [b] [c] [e]
[b]: [a] [c]
[c]: [a] [b] [d] [e]
[d]: [c] [e]
[e]: [a] [c] [d]

이때, 탐색 시작 위치를 d라고 가정하자.

먼저 d를 탐색하고 방문처리를 해준다.

d에서는 c로 가서 방문처리를 해준다.

c에서는 a로가서 a를 방문처리를해준다.

a에서는 b로가서 b를 방문처리를 해준다.

b에서는 a와 c 모두 방문 한 곳이다. 이때는 이전 정점인 a로가서 b, c, e를 탐색하고 e가 방문한 곳이 아니므로 방문처리를 해준다.

이때 종료 조건을 정해주어야하는데, 종료 조건은 모든 정점에서의 인접리스트를 모두 탐색했으나 방문처리가 되지 않은 곳을 발견하지 못할 경우 종료하도록 정해준다.

(최상위 정점까지 갔음에도 방문처리가 되지 않은 곳을 발견할 수 없다면)=>스택이 빌 경우

BFS가 인접리스트 방식으로 나타낸 그래프에서 작동하는 방식을 알아보자. 아래와 같은 그래프가 있다고 가정하자.

[a]: [b] [c] [e]
[b]: [a] [c]
[c]: [a] [b] [d] [e]
[d]: [c] [e]
[e]: [a] [c] [d]

이때, 탐색 시작 위치를 d라고 가정하자.

먼저, 큐에 d를 삽입하고 방문처리를 해준뒤, d의 인접 정점들(c,e)을 모두 차례대로 큐에 추가하며 방문처리를 해준다. 그리고 d를 큐에서 뺀다. 탐색현황(d->c->e) 현재큐: c e

큐에서 c를 빼주며 c에서 탐색시작.

c의 인접정점들 중 방문처리 되지 않은 정점들(a,b)을 모두 추가 및 방문처리를 해준다.

탐색현황(d->c->e->a->b) 현재큐: e a b

큐에서 e를 빼주며 e에서 탐색시작.

e의 인접정점들 중 방문처리 되지 않은 정점들(존재X)을 큐에 추가해주고 방문처리를 해준다. 탐색현황(d->c->e->a->b) 현재큐: a b

큐에서 a를 빼주며 a에서 탐색시작.

a의 인접정점들 중 방문처리 되지 않은 정점들(존재X)을 큐에 추가해주고 방문처리를 해준다. 탐색현황(d->c->e->a->b) 현재큐: b

큐에서 b를 빼주며 b에서 탐색시작.

b의 인접정점들 중 방문처리 되지 않은 정점들(존재X)을 큐에 추가해주고 방문처리를 해준다. 탐색현황(d->c->e->a->b) 현재큐: X

큐에 아무것도 남아있지 않으므로 함수 종료

이번시간에는 저번시간에 배운 DFS와 BFS를 다른 예제를 가지고 공부해 보는 시간을 가졌다.

다음시간에는 DFS와 BFS를 C언어로 구현해보는 시간을 가지도록 하겠다.

혹시 이해가 어렵거나 잘못된 부분이 있다면 언제든지 댓글을 달아주시면 감사하겠습니다!