bfs.md

너비 우선 탐색(BFS, Breadth-First Search)

너비 우선 탐색

너비 우선 탐색 BFS란 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어 특정 도시에서 다른 도시로 갈 수 있는지, 전자회로에서 특정 단자와 단자가 서로 연결되어 있는지를 탐색하는 알고리즘이다.

BFS에서의 노드 탐색 순서

너비 우선 탐색이기 때문에 깊이가 가장 얕은 노드부터 모두 탐색한뒤 깊이가 깊은 노드를 탐색하는 방법.
즉, 그림에서 깊이가 1인 노드1과 2를 먼저 탐색한뒤, 깊이가 1인 노드를 모두 탐색하였으므로 깊이가 2인 노드인 노드3 4 5 6을 탐색하는 순서다.

BFS 특징

• 두 노드 사이의 최단경로를 탐색할 때 활용하기 좋은 방식이다. 멀리 떨어진 노드는 나중에 탐색하는 방식이기 때문
• 큐를 활용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색한다. 선입 선출의 방식을 활용해야 하기 때문에 큐를 활용한다.

BFS 구현 알고리즘

1. 루트노드에서 시작한다.
2. 루트노드와 인접하고 방문된적 없고, 큐에 저장되지 않은 노드를 Queue에 넣는다.
3. Queue에서 dequeue하여 가장 먼저 큐에 저장한 노드를 방문한다.

1. 1번에서 루트노드에 방문하고
2. 2 3 4 5에서 인접하고 방문된적 없으며 큐에 저장되지 않은 노드를 큐에 저장한다.
3. 6에서 가장 먼저 큐에 저장된 1번노드로 이동해 인접 노드들의 조건을 확인한다.

이 방식을 큐에 저장된 노드가 없을 때 까지 반복한다.

그래프 구현방색

1. 인접 행렬
2. 인접 리스트

예를 들어보자

위와 같은 그래프를 구현할 때 다음과 같이 인접행렬과 인접리스트로 구현할 수 있다.
인접행렬은 이차원배열, 인접리스트는 링크드리스트 배열, 어레이리스트 배열, 어레이리스트를 저장하는 어레이리스트 등과 같은 방식으로 구현할 수 있다.

BFS를 인접 행렬로 구현한 코드

인접 행렬로 구현할 때 필요한 구조

1. 인접행렬 배열
2. 방문여부 배열
3. 큐
4. 방문한 노드를 순서대로 저장하는 배열

static void bfs(int node) {
	BFSisVisited[node] = true;  //노드방문여부를 true로 저장
	BFSvisitArr.add(node);   //방문한 노드를 순서대로 저장하는 리스트에 해당노드 추가
	for( int i = 1 ; i <= nodeNum ; i++) {
		if( graph[node][i] == 1 && BFSisVisited[i] == false && queue.contains(i)==false) {
           		//인접, 방문된적X, 큐에저장되지X 를 만족하는 노드를 큐에 추가
			queue.add(i);
		}
	}	
	if(!queue.isEmpty())
		bfs(queue.poll());   //큐에 가장 먼저 저장한 노드를 방문
}

인접행렬로 구현한 BFS의 시간복잡도 : O(N^2)

BFS를 인접리스트로 구현한 코드

인접리스트로 구현할 때 필요한 구조

1. 인접 리스트
2. 방문여부 배열
3. 큐
4. 방문한 노드를 순서대로 저장하는 배열

static void bfs(int node) {
	BFSisVisited[node] = true;  //노드방문여부를 true로 저장
	BFSvisitArr.add(node);   //방문한 노드를 순서대로 저장하는 리스트에 해당노드 추가
	for( int i = 0 ; i < graph[node].size() ; i++ ) {   
		//graph[node]에 인접한 노드만 저장되어있음
		int adjNode = graph[node].get(i);   
		if(BFSisVisited[adjNode] == false && queue.contains(adjNode) == false) {
			//방문된적X, 큐에저장되지X 를 만족하는 노드를 큐에 추가
			//adjNode에는 인접노드만 저장되므로 인접조건O
			queue.add(adjNode);
		}				
	}		
	if(!queue.isEmpty())
		bfs(queue.poll());   //큐에 가장 먼저 저장한 노드를 방문
}

인접리스트로 구현한 BFS의 시간복잡도 : O( N + E )