자료구조와 알고리즘 BFS (INTRODUCTION TO ALGORITHMS)

소개글

자료구조와 알고리즘 BFS (INTRODUCTION TO ALGORITHMS)에 대한 보고서 자료입니다.

목차

1.프로그래밍 소스
2.출력화면

본문내용

);
cout<<" d[u]의 변화 과정 \t\t\t pi[u]의 변화과정\n";
while(!Q.empty()){
Dprint();
cout<<"\t|\t";
PIprint();
cout<<"\n";
u=Q.front();
Q.pop();
for(int i=u-1;i<12;i++)
if(adj[u-1][i]==1){
v=i+1;
if(color[v-1]==0){
color[v-1]=2;
d[v-1]=d[u-1]+1;
pi[v-1]=u;
Q.push(v);
}
}
color[u-1]=3;
}
};
강의 자료에 있는 BFS의 의사코드를 C++코드로 바꾼 것이다. BFS의 진행 과정은
우선 모두 vertex의 색깔이 흰색(코드에서는 '0')이었던 상태에서 Starting Point의
값인 S의 color만 회색(코드에서는 '1')으로 바꾼다. 그리고 무한대를 대신해 '99'의 값을
집어넣었던 d배열에는 시작을 나타내는 '0'을 지정한다. 또한 부모를 나타내는 pi배열은
시작 값 s의 부모가 존재하지 않기에 0을 지정한다.
이후 QUEUE를 통해 S(소스에선 '1')를 집어넣고 QUEUE가 비어질 때 까지 While문을
돌린다. While문 내부에는 Q 내부에 있던 맨 아래 값(DEQUEUE시에 나올 값)을 u라는
변수에 옮겨주고 그에 연결된 인접 행렬을 찾아 v라는 변수에 넣어준다.
v라는 변수를 찾으면 v의 color이 무슨 색인지 확인(열어 본 것인지 확인하는 것)해 보고
White(열어보지 않은 것)이라면 color을 GRAY(소스에서 '1')로 바꿔주고 d[v]에 d[u]+1을
넣어 준다. 배열의 시작은 '0'이고 여기서 s의 값은 '1'이라는 점에서 배열 내부의 +1 연산
을 잘 해주어야 한다. 다음으로 부모 Vertex가 u라는 것을 저장하기 위해 pi배열에 u를
넣어준다. 그 후 v를 Q 내부에 넣어주면 for문은 끝나고, u의 color를 Black (이제 이
Vertex에는 볼일 없음! 이라고 Check한 것)으로 바꿔주면 While문이 한번 다 지나간
것이다. BFS는 이런 식으로 진행 된다.
int main()
{
CBFS bfs;
bfs.BFS(12,1);
return 0;
}
마지막으로 main 함수는 클래스로 지정한 CBFS의 생성자를 bfs로 지정한 후
BFS를 호출하면 끝난다. 여기서 '12'는 Vertex의 수이고, '1'은 Starting Point이다.
출력 화면

키워드

BFS,   자료구조,   알고리즘,   프로그래밍 소스