[알고리즘] 너비 우선 탐색(BFS : Breadth First Search) 알고리즘

너비 우선 탐색 알고리즘이란?

 

한 노드에서 인접한 노드을 우선으로 탐색하는 방법으로 그림과 같은 그래프가 주어졌을 때, 넓게 탐색한다.

BFS는 큐로 구현할 수 있고 주로 두 노드 간의 최단 경로를 찾을 때 사용할 수 있다.

 

너비 우선 탐색 과정

 

1) 시작 노드를 큐에 넣는다.

 

 2) 큐에서 노드 하나를 꺼내고 꺼낸 노드와 인접한 노드를 모두 큐에 넣는다

 

 3) 다시 큐에서 노드 하나를 꺼내 인접한 노드를 큐에 모두 넣는다.

 

4) 큐에 더 이상 노드가 없을 때까지, 즉, 인접한 노드가 존재하지 않을 때까지 반복한다.

 

 

너비 우선 탐색 구현

너비 우선 탐색을 소스코드로 구현하기 위해서는 먼저 그래프를 인접행렬로 만들어주어야한다.

 

인접행렬?

인접행렬이란 그래프가 주어졌을 때, 각 노드와의 연결관계를 이차원 행렬로 나타낸 것이다.

인접행렬을 a[n][m]이라고 할 때,

a[i][j]는 노드 i에서 노드 j로가는 간선을 의미하며 간선이 있을 경우 1, 없을 경우 0으로 나타낸다.

만약, 그래프가 가중치 그래프라면 1대신 가중치 w를 넣어준다.

 

즉, 두 노드 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 이루어진 2차원 배열을 만든다.

그래프

인접행렬

JAVA

package algorithm;

import java.util.*;

public class bfs {
	static int n;
	static int[][] map;
	static boolean[] visit;
	
	public static void bfs(int x) {
		Queue <Integer> q = new LinkedList<>();
		q.add(x);
		visit[x] = true;
		
		while(!q.isEmpty()) {
			x = q.poll();
			System.out.print((x + 1) + " ");
			
			for(int i = 0; i < n; i++) {
				if(map[x][i] == 1 && visit[i] == false) {
					q.add(i);
					visit[i] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		map = new int[n][n];
		visit = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		bfs(0);
	}
}