BFS(너비 우선 순회)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

Graph Traversal(그래프 순회)

Traversal(순회) : 그래프의 모든 노드들을 방문하는 일

대표적 두 가지 방법 

- BFS(Breath-First Search, 너비우선순회)

- DFS(Depth-First Search, 깊이우선순회)

BFS(Breath-First Search, 너비우선순회)

맹목적 탐색방법의 하나로 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 탐색하는 방법이다.

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

장점 : 

- 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점 : 

- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.

- 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.

- 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

큐를 이용한 너비우선순회

1. Check the start node;

2. insert the start node into the queue;

while the queue is not empty do
	remove a node v from queue;
	for each unchecked neighbour w of v do
		check and insert w into the queue;

너비우선순회 의사코드

BFS(G, s){
	Q <- 0;
	Enqueue(Q, S)
	while Q != 0 do
		u <- Dequeue(Q)
		for each v adjacent to u do
			if v is unvisited then
				mark v as visited;
				Enqueue(Q, v);
			end.
		end.
	end.
}

BFS와 최단경로

- S에서 Li에 속한 노드까지의 최단 경로 길이는 i이다.

- 여기에 경로의 길이는 경로에 속한 에지의 개수를 의미한다.

- BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.

- 입력 : 방향 혹은 무방향 그래프 G=(V, E) 그리고 출발노드 s∈V

- 출력 : 모든 노드 v에 대해서

d[v] = S로 부터 v까지의 최단 경로의 길이(에지의 개수)

[v] = S로 부터 v까지의 최단 경로 상에서 v의 직전 노드(predecessor)

최단거리 의사코드

BFS(G, s){
	Q <- 0;
	for each node u do
		d[u] <- -1;
		π[u] <- null;

	end.
	d[s] <- 0, π[s] <- NIL;

	Enqueue(Q, s);
	while Q != 0 do	// while문을 한 번 돌때마다 큐에서 하나를 꺼내므로 while 문은 최대 n번 돈다.
		u <- Dequeue(Q)
		for each v adjacent to u do	// 인접리스트로 구현할 경우 for문은 각 노드 v에 대해서 degree(v)번 돈다.
			if(d[v] == -1) then
				d[v] <- d[u]+1;
				π[v] <- u;

				Enqueue(Q, v);	// unchecked 노드만 queue에 들어갈 수 있으므로 어떤 노드도 큐에 두번 들어가지 않는다.
		end.
	end.
}

최단거리 출력

PRINT-PATH(G, s, v){	// 출발점 s에서 노드 v까지의 경로 출력하기
	if v=s then
		print s;
	else if π[v] = null then
		print "no path from s to v exists";
	else
		PRINT-PATH(G, s, π[v]);
		print v;
	end.
}

- 그래프가 disconnected 이거나 혹은 방향그래프 라면 BFS에 의해서 모든 노드가 방문되지 않을 수도 있음

- BFS를 반복하여 모든 노드 방문

BFS-ALL(G){
	while there exists unvisited node v
		BFS(G, v);
}

시간복잡도

∑ degree(v) = 2m 이므로 O(n+m)

소스 코드(Java)