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

 

(나만의)구분 특징

• 루트로부터 가까운 것 부터 검색
• 찾고자 하는 노드까지의 경로가 여러개일지라도 최단경로임을 보장 가능

 

알고리즘 작성순서

1. 인접행렬 VS 인접리스트 선택(그래프 정보 저장용)
2. 주어진 그래프 정보 입력
3. Queue를 사용한 BFS 알고리즘 구현

 

코드예시

 

인접리스트 사용시(Queue)

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BFS_LinkedList {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//---Graph정보 저장시작---//
		int nodeTotal = sc.nextInt();
		int edgeTotal = sc.nextInt();
		int startNode = sc.nextInt();
		
		boolean[] visited = new boolean[nodeTotal + 1];
		
		LinkedList<Integer> adjList[] = new LinkedList[nodeTotal + 1];
		
		for(int i=1; i<=nodeTotal; i++) {
			adjList[i] = new LinkedList<Integer>();
		}
		
		for(int i=0; i<edgeTotal; i++) {
			int node1 = sc.nextInt();
			int node2 = sc.nextInt();
			
			adjList[node1].add(node2);
			adjList[node2].add(node1);
		}
		
		for(int i=1; i<=nodeTotal; i++) {
			Collections.sort(adjList[i]);
		}
		//!---Graph정보 저장끝---!//
		
		System.out.println("BFS(인접리스트) : ");
		bfs_list(startNode, adjList, visited);
		
	}

	private static void bfs_list(int nodeOnCheck, LinkedList<Integer>[] adjList, boolean[] visited) {
		Queue<Integer> queue = new LinkedList<Integer>();
		visited[nodeOnCheck] = true;
		queue.add(nodeOnCheck);
		
		while(queue.size() != 0) {
			nodeOnCheck = queue.poll();
			System.out.println(nodeOnCheck + " ");
			
			Iterator<Integer> iterator = adjList[nodeOnCheck].listIterator();
			while(iterator.hasNext()) {
				int nextNode = iterator.next();
				if(!visited[nextNode]) {
					visited[nextNode] = true;
					queue.add(nextNode);
				}
			}
		}
	}

}

 

인접행렬 사용시(Queue)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BFS_Array {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//---Graph정보 저장시작---//
		int nodeTotal = sc.nextInt();
		int edgeTotal = sc.nextInt();
		int startNode = sc.nextInt();
		
		boolean[] visited = new boolean[nodeTotal + 1];
		
		int[][] adjArray = new int[nodeTotal + 1][nodeTotal + 1];
		
		for(int i=1; i<=nodeTotal; i++) {
			for(int j=1; j<=nodeTotal; j++) {
				int node1 = sc.nextInt();
				int node2 = sc.nextInt();
				
				adjArray[node1][node2] = 1;
				adjArray[node2][node1] = 1;
			}
		}
		//!---Graph정보 저장끝---!//
		
		System.out.println("BFS(인접행렬): ");
		bfs_array(startNode, adjArray, visited);
	}

	private static void bfs_array(int startNode, int[][] adjArray, boolean[] visited) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(startNode);
		visited[startNode] = true;
		
		while(queue.size() != 0) {
			int nodeOnCheck = queue.poll();
			System.out.println(nodeOnCheck + " ");
			
			for(int i=1; i<adjArray.length; i++) {
				if(adjArray[nodeOnCheck][i] == 1 && !visited[i]) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}
	}
	
}

 

 

참고 블로그 : https://minhamina.tistory.com/22?category=837168