목차
1.프로그래밍 소스
2.출력화면
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이다.
출력 화면
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이다.
출력 화면
추천자료
- 프로그래밍 언어의 발전사
- [C 프로그래밍] C로 배우는 프로그래밍 기초 12장 이해점검 및 프로그램문제 풀이
- [C 프로그래밍] C로 배우는 프로그래밍 기초 13장 이해점검 및 프로그램문제 풀이
- [C 프로그래밍] C로 배우는 프로그래밍 기초 14장 이해점검 및 프로그램문제 풀이
- [C 프로그래밍] C로 배우는 프로그래밍 기초 16장 이해점검 및 프로그램문제 풀이
- [C 프로그래밍] C로 배우는 프로그래밍 기초 18장 이해점검 및 프로그램문제 풀이
- [MFC 프로그래밍]미로찾기 프로그래밍(MFC, Visual C, 좌수법)
- 프로그래밍 실습
- 프로그래밍 실습
- 프로그래밍 실습 4.26
- [독후감] “ 행복한 프로그래밍 [컴퓨터 프로그래밍 미학 오디세이] ” 를 읽고 나서..
- 프로그래밍기초 및 실습 설계과제1 - 1. 24시간제로 시간을 입력하면 오전과 오후를 AM, PM ...
- 프로그래밍 언어 및 실습 - 헤더 파일 및 함수 정리
- [과제] 소켓프로그래밍 - TCP/IP를 이용한 소켓 프로그래밍
소개글