Graph BFS with queue

<C언어로 쉽게 풀어쓴 자료구조 > 내용

 

1. 개념

너비 우선 탐색( BFS )은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는

정점을 나중에 방문하는 순회 방법이다.

​ 

너비 우선 탐색을 위해서는 방문한 정점들을 차례로 저장한 후,

꺼낼 수 있는 자료 구조인 큐가 필요하다.

큐는 앞에서 만든 것을 이용할 것이다.

즉, 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고,

더 이상 방문할 인접 정점이 없는 경우에는 큐의 앞에서 정점을 꺼내어

그 정점과 인접한 정점들을 모두 차례대로 방문하게 된다.

초기 상태의 큐에는 시작 정점만이 저장되고,

너비 우선 탐색 과정은 큐가 소진될 때까지 계속한다.

여기에서도 pVisit배열을 쓴다.

 

너비 우선 탐색을 그림으로 보자.

아래에 임의의 그래프가 주어졌다고 가정하자.

[그림 1]

위의 그래프의 시작정점을 A라 두고, BFS를 진행하자.

 

[그림 2]

[그림 3]

[그림 4]

[그림 5]

[그림 6]

[그림 7]

[그림 8]

[그림 9]

[그림 10]

위 [그림 2]의 그래프를 방문한다고 가정하면

먼저 시작 정점A를 방문한다.

다음에는 정점A와 인접 정점인 {B,C,E}를 차례대로 방문한다.

다음으로 정점{B,C,E}에 인접한 정점들을 검사하여 아직 방문이 안된 정점이 있으면

방문한다.

아직 방문이 안된 정점은 D뿐 이다.

따라서 정점D가 방문이 되고, 탐색은 종료된다.

 

정점이 방문될 때마다, 큐에 방문된 정점을 삽입하고,

더 이상 방문할 인접 정점이 없는 경우 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을

모두 차례대로 방문하게 된다.

초기 상태의 큐에는 시작 정점만이 저장되고,

너비 우선 탐색 과정은 큐가 소진될 때까지 계속한다.

아래의 너비 우선 탐색 알고리즘 의사코드를 적용시키면, 아래와 같다.

먼저 시작정점A를 방문한 다음, 큐에 삽입된다.

while루프에서 큐가 공백상태가 아니므로, 큐에서 요소를 하나 삭제하게 되고 정점A를 추출한다.

for루프에서 인접한 정점인 B,C,E가 차례대로 방문되면서 동시에 큐에 삽입된다.

다시 while루프 처음으로 와서 큐에서 정점B가 추출되고, 정점B에 인접한 정점{A,C}가 조사된다.

하지만 정점 {A,C}는 이미 방문 되었으므로, for 루프는 끝나게 되고

다시 정점C를 큐에서 꺼내어 정점C에 인접한 정점인 {B,D,E}가 조사되고

이 중에서 정점D는 방문되지 않았으므로, 방문되고 큐에 삽입된다.

다시 큐에서 정점E를 꺼내어 인접한 정점들을 조사하지만, 이미 방문 되었고,

마지막으로 정점D를 큐에서 꺼내어 조사를 하지만, 역시 이미 인접 정점들은 다 방문이 된 상태이다.

드디어 큐가 공백 상태가 되고 탐색이 종료 된다.

 

2. 너비 우선 탐색 알고리즘

 

3. BFS 함수의 구현

메인 함수

프로그램 실행 결과

4. 헤더 파일 & 소스 파일

common.h

0.00MB

Graph.c

0.00MB

Graph.h

0.00MB

main.c

0.00MB

Queue.c

0.00MB

Queue.h

0.00MB