너비 우선 탐색 Breath-first Search BFS

너비 우선 탐색

시작점에서 도달 가능한 모든 간선을 탐색하여 찾는 과정

탐색을 하면서 시작점으로부터 거리를 계산한다.

탐색을 하면서 직전 정점의 위치를 저장한다. (거쳐온 정점을 기록한다.)

탐색을 하면서 정점의 상태를 변환한다. 

• 초기화  : not discovered         = white
• 발견한 정점 : discovered         = gray 
• 완료된(방문한) 정점 : finished   = black

 

슈도코드

1. 주어진 모든 Graph를 초기화

      * 정점의 상태 : 초기화(white)

      * 시작점으로부터의 거리 : ∞

      * 바로 직전의 정점 : 초기화(NULL)

2. 시작 위치 저장

      * 시작 정점의 상태 : 발견(gray)

      * 시작점으로부터의 거리 : 0

      * 바로 직전의 정점 : NULL 

      * Queue에 방문한 경로에 현재위치를 저장

3. 모든 경로 탐색 

     while {

         현재위치를 방문한 경로를 저장한 Queue에서 뽑아냄.

         for(현재 정점과 이어진 정점들을 탐색){

              if (정점의 상태 == white){

                *탐색된 정점의 상태를 gray(발견)으로 변경

                *시작점으로부터의 거리 + 1

                *바로 직전의 정점에 현재 위치를 저장

                *탐색된 정점을 방문한 경로를 저장한 Queue에 저장 

             }          

         }

        현재 위치 정점의 상태를 Black(방문)으로 변경

    }

 

시간복잡도

초기화 시간 : Ο(노드갯수)

그래프 탐색 시간 :  Ο(노드갯수 + 간선갯수)

• 정점은 최대 1번 탐색한다.
• 간선은 최대 2번 탐색한다.

 

전체 수행시간 

Ο( N + E )

 

구현 JAVA

[인접리스트]

package algorithm;

import java.util.*;

public class bfs {
	
	public static void main(String[] args) {
		//인접리스트를 이용하여 그래프 구현 
		int[][] graph = { {},
				{ 2, 3, 4 },
				{ 1, 5, 6 },
				{ 1, 7 },
				{ 1, 8 },
				{ 2 },
				{ 2, 9 },
				{ 3 },
				{ 4 },
				{ 6 } };
		//정점의 방문여부(정점의 상태)를 저장할 배열
		boolean[] visited = new boolean[10];
		//시작점부터 정점까지의 거리
		int distance = 0;
		
		bfs f = new bfs();
		f.bfs(1, graph, visited, distance);
		
	}

	public void bfs(int now, int[][] graph, boolean[] visited, int distance) {
		
		StringBuilder route = new StringBuilder(); //경로 방문순서
		
		//시작 위치를 저장
		Queue<Integer> queue = new LinkedList<Integer>();
		visited[now] = true; //시작 정점 상태
		queue.add(now);
		
		//경로 탐색
		while(queue.size() > 0) {
			//현재위치를 방문한 경로를 저장한 QUEUE에서 추출
			now = queue.poll();	
			for(int v : graph[now]) {
				//정점의 상태가 미방문 false이면 탐색
				if(!visited[v]) {
					visited[v] = true;					
					queue.add(v);					
					route.append(v); //방문한 경로 저장					
				}				
			}			
		}
		
		System.out.println(route.toString());
		
	};

}

23456789

 

[인접배열]

package algorithm;

import java.util.*;

public class bfs2 {
	
	public static void main(String[] args) {
		//인접리스트를 이용하여 그래프 구현 
		int[][] graph = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
				  { 0, 0, 1, 1, 1, 0, 0, 0, 0, 0},
				  { 0, 1, 0, 0, 0, 1, 1, 0, 0, 0},
				  { 0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
				  { 0, 1, 0, 0, 0, 0, 0, 0, 1, 0},
				  { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
				  { 0, 0, 1, 0, 0, 0, 0, 0, 0, 1},
				  { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
				  { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
				  { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}};
		//정점의 방문여부(정점의 상태)를 저장할 배열
		boolean[] visited = new boolean[10];
		//시작점부터 정점까지의 거리
		int distance = 0;
		
		bfs2 f = new bfs2();
		f.bfs(1, graph, visited, distance);
		
	}

	public void bfs(int now, int[][] graph, boolean[] visited, int distance) {
		
		StringBuilder route = new StringBuilder(); //경로 방문순서
		
		//시작 위치를 저장
		Queue<Integer> queue = new LinkedList<Integer>();
		visited[now] = true; //시작 정점 상태
		queue.add(now);
		
		//경로 탐색
		while(queue.size() > 0) {
			//현재위치를 방문한 경로를 저장한 QUEUE에서 추출
			now = queue.poll();	
			
			for(int i = 1; i< graph.length; i++) {
				//정점의 상태가 미방문 false이면 탐색
				if( graph[now][i] == 1 && !visited[i]) {
					visited[i] = true;					
					queue.add(i);					
					route.append(i); //방문한 경로 저장					
				}				
			}			
		}
		
		System.out.println(route.toString());
		
	};
}

23456789

 

출처

• 너비 우선 탐색, 위키백과 
• 컴퓨터 알고리즘 기초 14강 넓이우선탐색, T아카데미