[Algorithm] 그래프 탐색 BFS(너비 우선 탐색)에 대해서 with Java

과거에 나는 DFS와 BFS에 대해서 간단하게 정리한 경험이 있다. 이번에는 다시 한번 더 공부겸 좀 더 많은 것들을 기록하고자 다시 한번 더 포스팅을 해보자.

https://superohinsung.tistory.com/176

[DataStructure] 트리(Tree)

 

그래프 탐색(Graph Traversal)은 그래프의 모든 정점을 방문하는 과정이다.

 

BFS (Breadth-First Search)란?

BFS는 시작 정점에서 가까운 정점부터 차례대로 탐색하는 방식이다.
BFS는 큐(Queue)를 활용하여 탐색하며, 최단 경로 문제에서 자주 사용된다.

BFS의 동작 방식:

1. 시작 노드를 큐(Queue)에 넣고 방문 처리
2. 큐에서 노드를 꺼내 인접한 노드를 모두 큐에 넣음
3. 더 이상 방문할 노드가 없을 때까지 반복

BFS는 DFS와 다르게 모든 정점을 한 단계씩 방문하기 때문에 최단 경로 문제에 유용하다.

 

BFS 구현 방식

BFS를 구현하는 방법에는 인접 행렬(Adjacency Matrix) 방식과 인접 리스트(Adjacency List) 방식 두 가지가 있다.

방식	시간 복잡도	특징
인접 행렬 (Adjacency Matrix)	O(V^2)	메모리 사용 많음 (V x V 크기 배열 필요)
인접 리스트 (Adjacency List)	O(V + E)	메모리 사용 적음 (필요한 연결 정보만 저장)

 

인접 리스트(Adjacency List)를 이용한 BFS 구현

주요 Point

• 각 정점의 연결 정보를 Node 객체로 관리
• 연결 리스트 형태로 저장하여 메모리를 절약
• 시간 복잡도: O(V + E) (정점과 간선 개수의 합)

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class AdjListSearch_BFS {

	private static class Node {
		public int vertex;  // 정점 번호
		public Node link;  // 연결된 정점 (리스트 형태)

		public Node(int vertex, Node link) {
			this.vertex = vertex;
			this.link = link;
		}
	}

	private static int V;  // 정점 개수
	private static int E;  // 간선 개수
	private static Node[] adjList;  // 인접 리스트

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();  // 정점 개수 입력
		E = sc.nextInt();  // 간선 개수 입력
		
		adjList = new Node[V];  // 인접 리스트 초기화 (null 상태)

		int from, to;
		for (int i = 0; i < E; i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			
			// 무향 그래프 (양방향 간선 추가)
			adjList[from] = new Node(to, adjList[from]);
			adjList[to] = new Node(from, adjList[to]);
		}
		
		bfs(0);  // BFS 시작 (0번 정점부터 탐색)
	}

	// BFS 탐색 함수
	private static void bfs(int start) {
		Queue<Integer> queue = new ArrayDeque<>();
		boolean[] visited = new boolean[V];

		queue.offer(start);  // 큐에 넣어 첫번째 정점 방문 예약
		visited[start] = true;  // 방문 체크

		int current = 0;  // 현재 정점번호
		while (!queue.isEmpty()) {
			current = queue.poll();  // 큐에서 꺼내기
			System.out.print((char) (current + 65) + " ");  // 정점 출력 (A, B, C...)

			// 연결된 정점들을 순차적으로 방문
			for (Node temp = adjList[current]; temp != null; temp = temp.link) {
				if (!visited[temp.vertex]) {
					queue.offer(temp.vertex);  // 큐에 추가
					visited[temp.vertex] = true;  // 방문 체크
				}
			}
		}
	}
}

 

인접 행렬(Adjacency Matrix)를 이용한 BFS 구현

주요 Point

• 2차원 배열을 사용하여 정점 간 연결 정보를 저장
• 시간 복잡도: O(V^2) (모든 정점을 순회하며 확인해야 함)
• 작은 그래프에는 유리하지만, 큰 그래프에서는 메모리 사용이 많음

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class AdjMatrixSearchTest_BFS {
	
	private static int V;  // 정점 개수
	private static int E;  // 간선 개수
	private static int[][] adjMatrix;  // 인접 행렬

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();
		
		adjMatrix = new int[V][V];  // 초기화 (0으로 설정)

		int from, to;
		for (int i = 0; i < E; i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			
			// 무향 그래프 (양방향 간선)
			adjMatrix[to][from] = adjMatrix[from][to] = 1;
		}

		bfs(0);  // BFS 시작
	}

	// BFS 탐색 함수
	private static void bfs(int start) {
		Queue<Integer> queue = new ArrayDeque<>();
		boolean[] visited = new boolean[V];

		queue.offer(start);  // 큐에 넣어 첫번째 정점 방문 예약
		visited[start] = true;  // 방문 체크

		int current = 0;  // 현재 정점번호
		while (!queue.isEmpty()) {
			current = queue.poll();  // 큐에서 꺼내기
			System.out.print((char) (current + 65) + " ");  // 정점 출력

			// 모든 정점 탐색하여 인접 여부 확인
			for (int i = 0; i < V; i++) {
				if (adjMatrix[current][i] != 0 && !visited[i]) {
					queue.offer(i);  // 큐에 추가
					visited[i] = true;  // 방문 체크
				}
			}
		}
	}
}

 

예제 입력 및 실행 과정(공통)

입력

6 7
0 1
0 2
1 3
1 4
2 4
3 5
4 5

 

그래프 구조

    (0)
   /   \
 (1)   (2)
  | \   |
 (3) (4)
  |   |
 (5)---

 

BFS(0) → A → B → C → D → E → F

A B C D E F

 

시간 복잡도 비교

방식	시간 복잡도	메모리 사용량	특징
인접 행렬	O(V^2)	높음 (V x V 크기의 배열 필요)	빠르게 인접 여부 확인 가능
인접 리스트	O(V + E)	낮음 (E개 만큼의 연결 리스트)	메모리 절약 가능