bfs - 알고리즘

bfs - 알고리즘

너비 우선 탐색 알고리즘

 

 

위 트리를 vector함수로 구현한다

vector<int> a[10];

int main(void) {
	a[1].push_back(2);
	a[2].push_back(1);

	a[1].push_back(3);
	a[3].push_back(1);

	a[2].push_back(4);
	a[4].push_back(2);

	a[2].push_back(5);
	a[5].push_back(2);

	a[4].push_back(8);
	a[8].push_back(4);

	a[5].push_back(9);
	a[9].push_back(5); 

	a[3].push_back(6);
	a[6].push_back(3); 

	a[3].push_back(7);
	a[7].push_back(3);

	return 0;
}

 

a[10]vector 내 데이터

 

#include <iostream>
#include <queue>
#include<vector> 
using namespace std;
int number = 9;
int visit[9];//노드와 인접했는지 안했는지 검사결과를 담을 배열
vector<int> a[10];//트리를 만들 vector

void bfs(int start) {//start에 1을 넣음
	queue<int> q;//숫자를 정렬할 큐 생성
	q.push(start);//1을 큐에 넣음
	visit[start] = true;//visit[1] 에 1을 넣음

	while (!q.empty()) {//큐에 데이터가 없으면 정지
		int x = q.front();//큐의 가장 앞에 있는 값을 x값에 넣음
		q.pop();//1을 뺌
		printf("%d ", x);//1출력
		for (int i = 0; i < a[x].size(); i++) {//a[x].size는 a[1]의 크기를 말한다 2,3이 들어가있기때문에 값이2이다)
			int y = a[x][i];//a[1][0]의 값 2를 y에 넣음
			if (visit[y] == 0) {//visit[2]가 0이면 즉 2와 인접하지 않았다면
				q.push(y);//큐에 2를 넣고
				visit[y] = true;//visit[2]=1 2와 인접했으면 1 이라고 표시 
			}
		}
	}//반복
}
int main(void) {
	a[1].push_back(2);
	a[2].push_back(1);

	a[1].push_back(3);
	a[3].push_back(1);

	a[2].push_back(4);
	a[4].push_back(2);

	a[2].push_back(5);
	a[5].push_back(2);

	a[4].push_back(8);
	a[8].push_back(4);

	a[5].push_back(9);
	a[9].push_back(5); 

	a[3].push_back(6);
	a[6].push_back(3); 

	a[3].push_back(7);
	a[7].push_back(3);

	bfs(1);
	return 0;
}