14-3
BFS 구현
저번 시간에 우리는 DFS를 구현했다.
언급했던대로 이번 챕터에서 BFS를 구현할거다.
앞서 우리는 DFS에서 가장 중요한 DFShowGraphVertex 함수에서 해당 함수의 기능을 구현하는데 큰 역할을 한 재료 두개는 "연결 리스트"와 "Stack" 이였다.
이번에도 연결 리스트는 사용은 하지만, Stack 대신 방문 차례 기록을 위해 Queue를 사용할 것이다. (기억 안난다면 Ch.07 복습내용을 보고 오자. 조금 한지 오래되어서 기억이 안날수도있다.)
일단 Queue를 기억하고있다는 전제하에, 구현을 어떤 과정을 베이스로 해줄지 과정을 그림으로 그려보도록 하겠다.
위와 같은 그림으로 설명할거다. 왼쪽은 계속 봐온 비상연락망, 우측 상단은 방문 차례의 기록을 남기는 Queue, 우측 하단은 방문 정보의 기록을 남기는 배열.
자 일단. 시작점은 지율이다.
지율이를 시작으로 방문해줬으니, arr[지율] = 1로 바꿔준다. (1은 방문함 / 0은 방문한적 없음)
그 다음, 앞서 BFS의 기본 이론에서 설명했던 것처럼 자기와 연결된 친구들 (동수, 민석)에게 연락을 돌린다. 그와 동시에 arr[동수] = arr[민석] = 1을 만들어주고 Queue에 동수와 민석이를 넣어준다.
지율이는 왜 생략했냐고? 어짜피 첫 시작 넣고 동수랑 민석이 가자마자 Queue에서 빼줘야한다. 넘기자 그냥.
그 다음, 동수가 민석이보다 먼저 연락을 돌린다 가정하고 동수가 지민이에게 연락을 돌린다. 동수는 Queue에서 빼주고, 지민이를 Queue에 넣는다. 그리고 arr[지민] = 1.
그 다음은 뭘까? 대충 예측해보고, 아래 그림을 보도록 하자.
민석이에게 연결된 수정, 정희에게 연락을 돌릴 차례다. 그러면? 민석이는 Queue에서 빼준다. 그리고, 수정이와 정희를 Enqueue.
이후 arr[수정], arr[정희] = 1.
이후, 정희가 명석이에게 연락을 넣는다.
그러면 정희를 "지민", "수정"이는 더 연락을 취할 대상이 없으니 Queue에서 꺼내고, "정희"의 이름을 꺼내서 "명석"에게 연락을 돌리게 한다.
그러면, 끝!
..이 아니고, 명석이에게 연락이 들어갔으니 명석의 이름을 큐에 넣는다.
굳이 연결된 대상이 없는데 왜? 물론 그림으로 저렇게 봤으니 그렇지만, 혹시 코드로 봤다면 모른다. 명석이에게 연결된 "더 연락을 취해야 할 대상"이 남아있을지도 모르니까, 명석이까지 큐에 넣어서 확인해본다. 이후에 더 없으니, Dequeue!
이렇게, BFS에 따른 탐색이 끝난다.
코드는 DFS 구현 결과에서 DFShowGraphVertex만 BFShowGraphVertex로 바꿔주면 된다. 나머지는 큐를 참고한다는 것만 헤더파일에서 바꿔주면, 바꿀게 없다. 그래서, BFShowGraphVertex를 보이겠다.
모든 코드들 (풀버전)은 여기서 참고하자.
void BFShowGraphVertex(ALGraph *pg, int startV) { // 그래프의 정점 정보를 출력한다. (BFS 기반)
Queue queue;
int visitV = startV;
int nextV;
QueueInit(&queue);
VisitVertex(pg, visitV); // 시작 정점을 방문
// 아래 while문에서 모든 정점의 방문이 이뤄진다.
while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) { // visitV에 담긴 정점과 연결된 정점의 방문을 시도한다.
// visitV와 연결된 정점의 정보가 nextV에 담긴 상태에서 이하를 진행.
// 위의 LFirst 함수 호출 -> visitV에 연결된 정점 하나 get -> 이 정점의 정보를 nextV에 저장
// nextV에 담긴 정점의 정보로 방문 시도!
if (VisitVertex(pg, nextV) == TRUE) {
Enqueue(&queue, nextV);
}
while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE) {
if(VisitVertex(pg, nextV) == TRUE) {
Enqueue(&queue, nextV);
}
}
if (QIsEmpty(&queue) == TRUE) {
break;
} else {
visitV = Dequeue(&queue);
}
}
memset(pg->visitInfo, 0, sizeof(int) * pg->nextV);
}여기까지.
