Breadth First Search

1. Problem

- root에 대하여 너비 우선 탐색을 실행해보자.

- 너비 우선 탐색은 깊이보다 너비(같은 레벨의 노드)를 우선적으로 탐색하는 알고리즘이다.

- 탐색 결과는 root에서 가까운 것부터 나오게 된다.

- 최단 경로를 보장해야 할 때 사용한다.

- 주로 큐로 구현한다.

 

2. Input

1) int[][] graph

- 노드 간의 연결성 표현

2) int root

- root 노드의 값

 

3. Output

1) root에 대하여 너비 우선 탐색을 실행한 결과

 

4. Example

// 예시: 위 그래프가 주어졌을 때, 1부터 차례대로 방문한다.
// 한 번 방문한 노드는 다시 방문하지 않는다.                  	list		queue
// 첫 번째로, 1을 방문한다.                                	[1]		[]
// 1과 연결 되어 있는 노드 중 방문하지 않은 노드를 큐에 넣는다.	[1]		[2,3]
// 큐에서 2를 꺼낸다.                                      	[1,2]		[3]
// 2와 연결 되어 있는 노드 중 방문하지 않은 노드를 큐에 넣는다.	[1,2]		[3,4]
// 큐에서 3을 꺼낸다.                                      	[1,2,3]		[4]
// 3과 연결 되어 있는 노드 중 방문하지 않은 노드를 큐에 넣는다.	[1,2,3]		[4,6]
// 큐에서 4를 꺼낸다.                                      	[1,2,3,4]	[6]
// 4와 연결 되어 있는 노드 중 방문하지 않은 노드를 큐에 넣는다.	[1,2,3,4]	[6,5]
// 큐에서 6을 꺼낸다.                                      	[1,2,3,4,6]	[5]
// 6과 연결 되어 있는 노드 중 방문하지 않은 노드를 큐에 넣는다.	[1,2,3,4,6]	[5]
// 큐에서 5를 꺼낸다.                                      	[1,2,3,4,6,5]	[]
// 6과 연결 되어 있는 노드 중 방문하지 않은 노드를 큐에 넣는다.	[1,2,3,4,6,5]	[]
// 큐가 비어있게 되면 탐색을 종료한다.                       	[1,2,3,4,6,5]
// 같은 그래프에 대한 깊이 우선 탐색의 결과                     	[1,3,6,2,4,5]

 

5. Code

// 위 그래프를 2차원 배열로 표현
// graph[i][j] == 1 if (i+1)과 (j+1)이 직접 연결되어 있다면
//             == 0 if 자기 자신이라면
//             == -1 if (i+1)과 (j+1)이 직접 연결되어 있지 않다면
int[][] graph = {{0,1,1,-1,-1,-1},{1,0,1,1,-1,-1},{1,1,0,-1,-1,1},
                 {-1,1,-1,0,1,-1},{-1,-1,-1,1,0,-1},{-1,-1,1,-1,-1,0}};
boolean[] visited = new boolean[graph.length];
Queue<Integer> q = new LinkedList<>();
q.add(1); // root = 1
visited[0] = true;
while(!q.isEmpty()) {
    int n = q.remove();
    System.out.print(n+",");
    for(int i=0 ; i<graph[n-1].length ; i++)
        if(graph[n-1][i]==1 && !visited[i]) {
            q.add(i+1);
            visited[i] = true;
        }
}
// 출력 결과: 1,2,3,4,6,5,