[알고리즘] BFS

BFS(Breadth First Search)

 

너비우선탐색을 예제를 통해 알아본다.

queue를 사용하며 FIFO의 특징을 가지고 있으므로, push된 순서대로 front 값을 얻을 수 있다.

 

예제.

4 5 1
1 2
1 3
1 4
2 4
3 4
결과: 1 2 3 4

 

c언어.

bool map[1001][1001];
bool visit[1001];
bool queue[1001];
int front, rear;
int n;	//정점개수
int m;	//간선개수
int v;	//시작정점

void input(void)
{
	scanf("%d%d%d", &n, &m, &v);
	for(int i=1; i<=m; i++)
	{
		int x = 0, y = 0;
		scanf("%d%d", &x, &y);
		map[x][y] = map[y][x] = true;
	}
}

void BFS(int s)
{
	printf("%d ", s);
	visit[s] = true;
	queue[rear++] = s;
	while( front < rear )
	{
		s = queue[front++];
		for(int i=1; i<=n; i++)
		{
			if(map[s][i] == true && !visit[i])
			{
				printf("%d ", i);
				visit[i] = true;
				queue[rear++] = i;
			}
		}
	}
}

int main()
{
	input();
	BFS(v);
	printf("\n");
	return 0;
}

 

c++.

using namespace std;

queue q;
int graph[1001][1001];
int visit[1001];
int n;	//정점개수
int m;	//간선개수
int v;	//시작정점

void input(void)
{
	cin >> n >> m >> v;
	for(int i=1; i<=m; i++)
	{
		int x = 0, y = 0;
		cin >> x >> y;
		graph[x][y] = graph[y][x] = 1;
	}
}

void BFS(int s)
{
	q.push(s);
	visit[s] = 1;

	while(!q.empty())
	{
		s = q.front();
		q.pop();
		cout << s << " ";
		for(int i=1; i<=n; i++)
		{
			if(graph[s][i]==1 && !visit[i])
			{
				visit[i] = 1;
				q.push(i);
			}
		}
	}
}

int main()
{
	input();
	BFS(v);
	cout << endl;
	return 0;
}