[JAVA] 너비 우선 탐색 (BFS)

너비 우선 탐색은 시작 정점에 인접한 정점들을 모두 방문한 뒤에 이 정점들에 인접한 방문하지 않은 정점들을 모두 방문한다.

이 과정을 반복해 정점들을 시작 정점까지의 최단 경로의 길이 순서대로 방문한다.

만약 탐색이 종료된 후에 아직 방문하지 않은 정점들이 남아 있다면 그 정점들 중 한 정점에서 너비 우선 탐색을 시작한다.

 

너비 우선 탐색 알고리즘은 깊이 우선 탐색과 달리 재귀를 사용하여 작성할 수 없는 유형이다.

대신 너비 우선 탐색은 큐를 사용하여 쉽게 작성할 수 있다.

 

시간복잡도

- 인접 리스트: O(V+E)

- 인접 행렬: O(V^2)

 

알고리즘

알고리즘 BFSearch(G)

1 V에 있는 각 정점을 '방문 안함'으로 표시한다
2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 BFS(v)를 호출한다.

BFS(v)
1 v를 '방문함'으로 표시한다.
2 v를 큐의 끝에 추가한다.
3 큐가 비어 있지 않은 동안 다음을 수행한다.
  3.1 큐의 맨 앞에 있는 정점을 끄집어내어 element에 저장한다.
  3.2 element의 데이터를 출력한다.
  3.3 element에 인접한 모든 정점 w에 대해 
      w가 '방문 안함'으로 표시되어 있다면 w를 '방문함'으로 표시하고 w를 큐의 끝에 추가한다.

 

JAVA

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Node {
	int info;
	boolean visited;
	List<Node> neighbors;
	
	public Node(int info) {
		this.info = info;
		this.visited = false;
		this.neighbors = new ArrayList<>();
	}
	
	public void addNeighbors(Node neighborsNode) {
		this.neighbors.add(neighborsNode);
	}
	
	public List<Node> getNeighbors() {
		return neighbors;
	}
	
	public void setNeighbors(List<Node> neighbors) {
		this.neighbors = neighbors;
	}
	
	public String toString() {
		return "" + info;
	}
}

public class BreadthFirstSearch {
	private Queue<Node> queue;
	
	public BreadthFirstSearch() {
		queue = new LinkedList<Node>();
	}
	
	public void BFS(Node v) {
		v.visited = true;
		
		queue.add(v);
		
		while (!queue.isEmpty()) {
			Node element = queue.remove();
			
			System.out.print(element.info + " ");
			
			List<Node> neighbors = element.getNeighbors();
			
			for (int i = 0; i < neighbors.size(); i++) {
				Node w = neighbors.get(i);
				
				if (w != null && !w.visited) {
					w.visited = true;
					queue.add(w);
				}
			}
		}
	}
	
	public static void main(String arg[]) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		
		node1.addNeighbors(node2);
		node1.addNeighbors(node3);
		node1.addNeighbors(node5);
		node2.addNeighbors(node1);
		node2.addNeighbors(node3);
		node3.addNeighbors(node1);
		node3.addNeighbors(node2);
		node3.addNeighbors(node4);
		node3.addNeighbors(node5);
		node4.addNeighbors(node3);
		node4.addNeighbors(node6);
		node5.addNeighbors(node1);
		node5.addNeighbors(node3);
		node6.addNeighbors(node3);
		node6.addNeighbors(node4);

		BreadthFirstSearch bfsExample = new BreadthFirstSearch();
		
		System.out.println("너비 우선 탐색 실행 결과");
		bfsExample.BFS(node1);
	}
	
}