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

[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 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 getNeighbors() { return neighbors; } public void setNeighbors(List neighbors) { this.neighbors = neighbors; } public String toString() { return "" + info; } } public class BreadthFirstSearch { private Queue queue; public BreadthFirstSearch() { queue = new LinkedList(); } public void BFS(Node v) { v.visited = true; queue.add(v); while (!queue.isEmpty()) { Node element = queue.remove(); System.out.print(element.info + " "); List 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); } }

from http://pekahblog.tistory.com/184 by ccl(S) rewrite - 2021-12-14 13:28:04