BFS : 너비 우선 탐색 (Java)

너비 우선 탐색 또한 그래프 탐색 이론이다. 깊이 우선 탐색과의 차이점은, BFS는 현재 노드 기준 가장 가까운 노드들을 모두 거치고 지나간다.

특징으로는 1번, 재귀적으로 작동하지 않는다. 2번, 노드에 방문했던 사실을 체크해줘야 한다. 3번, 동일 깊이의 노드들을 선입선출을 기반으로 하는 큐에 넣어두었다가 사용한다.

이런 순서로! 엄밀히 말하면 같은 깊이의 노드들을 한 번에 처리하는 것은 아니지만. 

똑같이 인접 행렬로 구현한다.

 

알고리즘을 정렬해보면:

1. 시작 노드의 번호를 큐에 넣는다.

2. 큐에 있는 노드를 꺼낸다.

3. 해당 노드와 연결되어 있는 노드들 중에 방문하지 않은 노드들을 큐에 넣는다.

4. 큐가 비어있지 않으면 2~4번을 반복한다.

 

코드로 한 번 구현해보자. 

 

import java.util.*;
//재귀적으로 작동하지 않는 너비우선탐색
//1. 시작 노드를 큐에 넣고
//2. 큐에서 꺼낼 때 검사: 방문했는가? 했으면 패스
//3. 방문하지 않았다면 방문체크하고 검사: 행렬에서 간선이 있는지
//4. 있다면 큐에 넣기

class Graph1 {
	private int nodes, roads;
	private int[][] Graph;
	private boolean[] visited;
	
	public Graph1(int nodes, int roads) {
		this.nodes = nodes;
		this.roads = roads;
		this.visited = new boolean[nodes+1];
		this.Graph = new int[nodes+1][nodes+1];
	}
	
	//그래프에 값을 넣는 메서드 
	public void Graph_set(int start_node, int finish_node) {
		for(int i=0; i<roads; i++) {
			Graph[start_node][finish_node] = Graph[finish_node][start_node] = 1;
			}
	}
	
	public void bfs(int start_node) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start_node);
		int cur_node;
		//큐가 비어있지 않으면 반복 
		while(!q.isEmpty()) {
			//큐에서 가장 앞의 요소 꺼내기 
			cur_node = q.poll();
			//이미 방문했던 노드라면 패
			if(visited[cur_node]==true) {
				continue;
			}
			System.out.println(cur_node);
			//방문 
			visited[cur_node] = true;
			//해당 노드와 연결되어있고 방문하지 않은 노드가 있다면 모두 큐에 삽
			for(int next_node=1; next_node<=nodes; next_node++) {
				if(Graph[cur_node][next_node] != 0 && visited[next_node] == false) {
					q.add(next_node);
				}
			}
			
		}
	}
}
public class note_bfs {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int nodes = sc.nextInt();
		int roads = sc.nextInt();
		int start_node = sc.nextInt();
		Graph1 g = new Graph1(nodes, roads);
		for(int i=0; i<roads; i++) {
			g.Graph_set(sc.nextInt(), sc.nextInt());
		}
		sc.close();
		g.bfs(start_node);
		
	}
}