BFS 특징
- 너비 우선 탐색
- 큐의 FIFO(First In First Out) 성질을 이용하여 정점들을 차례로 탐색합니다.
- 그래프 탐색의 경우, 어떤 노드를 방문했는지 여부를 반드시 검사해야합니다.
- 재귀적으로 동작하지 않습니다.
BFS의사코드는 아래와 같습니다.
pseudo code
BFS(G, s)
for each u ∈ V - {s} do
color[u] ← WHITE
Π[u] ← NIL
d[u] ← ∞
color[s] ← GRAY
Π[s] ← NIL
d[s] ← 0
Q ← {s}
while Q ≠ ∅ do
u ← head[Q]
for each v in Adj[u] do
if color[v] = WHITE then
color[v] ← GRAY
Π[v] ← u
d[v] ← d[u] + 1
ENQUEUE(Q, v)
DEQUEUE(Q)
color[u] ← BLACK
BFS_adjList
BFS는 그래프를 탐색하는 방법중 하나입니다.
탐색할 그래프를 구현해봅시다.
- 그래프를 구성하기 위해서는 정점과 간선이 필요하므로 정점의 개수와 간선의 개수를 입력으로 받습니다.
- 각 정점의 방문여부를 기록하기 위한 배열객체와 adjList 를 생성해줍니다.
-
반복문을 이용해 각 인덱스에 정점에 연결된 정점들을 저장하기 위한 List객체를 생성해줍니다.
-
1-based Index를 사용하기 위해 visited[] 배열과 adjList의 크기는 모두 n+1로 생성해주었습니다.
무방향 그래프이므로, (u,v) = (v,u) 를 만족합니다.
만약 입력으로 (v1,v2) 가 들어온다면, v1에 연결된 정점이 v2임을 의미하고 adjList[v1]={v2}를 만족합니다. (u,v) = (v,u) 를 만족하므로, adjList[v2]={v1} 또한 만족해야 합니다.
위와 같이 입력으로 들어온 간선 정보를 각각의 u와 v를 대칭시켜 값을 넣어주면 됩니다.
BFS를 이용해 탐색할 때, 인접정점들을 큐에 넣어서 순차적으로 탐색하기 때문에 오름차순으로 정렬해주어야 합니다.
collections.sort()를 이용해 각각의 정점리스트를 정렬시켜줍니다.
BFS 구현
탐색중인 정점들을 처리할 큐를 생성해주었습니다.
시작 정점이 v이므로, visited[v]= true 상태로 바꾸어줍니다.
큐에 add해주고 탐색을 시작합니다.
BFS는 탐색중인 정점들을 큐에 넣고, 큐가 빌때까지 탐색을 진행합니다.
BFS는 FIFO이므로, 먼저 들어간 정점부터 차례대로 꺼내서 탐색합니다.
인접 정점 탐색
Iterator를 생성해 현재 정점에 연결된 인접 정점들을 순차적으로 탐색합니다.
인접 정점이 존재하는 동안 계속해 모든 인접정점을 모두 탐색할 때 까지 큐에 넣는 작업을 해줍니다.
무방향 그래프이기 때문에 (u,v)=(v,u)를 만족하므로 값을 걸러주지 않는다면 중복해서 큐에 집어넣기 때문에, visited[w] 값을 이용해 중복을 체크해주어야 합니다.
code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boolean visited[] = new boolean[n+1];
LinkedList<Integer>[] adjList = new LinkedList[n+1];
for(int i=0; i<=n; i++){
adjList[i] = new LinkedList<Integer>();
}
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
adjList[v1].add(v2);
adjList[v2].add(v1);
}
for(int i=0; i<=n; i++) {
Collections.sort(adjList[i]);
}
System.out.println("BFS 인접리스트 ");
bfs_list(v,adjList,visited);
}
public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited){
Queue<Integer> queue = new LinkedList<Integer>();
visited[v] = true;
queue.add(v);
while(queue.size()!=0){
v=queue.poll();
System.out.println(v + " ");
Iterator<Integer> iter = adjList[v].listIterator();
while(iter.hasNext()){
int w = iter.next();
if(!visited[w]){
visited[w] = true;
queue.add(w);
}
}
}
}
}BFS _ adjMatrix
모두 동일한데 인접리스트 부분만 배열로 선언하고 나머지 부분들을 바꾸어 주면 됩니다.
code
import java.util.*;
public class BFS_Array {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int v = sc.nextInt();
boolean visited[] = new boolean[n + 1];
int[][] adjArray = new int[n+1][n+1];
for(int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjArray[v1][v2] = 1;
adjArray[v2][v1] = 1;
}
System.out.println("BFS - 인접행렬");
bfs_array(v, adjArray, visited);
}
// BFS - 인접행렬
public static void bfs_array(int v, int[][] adjArray, boolean[] visited) {
Queue<Integer> q = new LinkedList<>();
int n = adjArray.length - 1;
q.add(v);
visited[v] = true;
while (!q.isEmpty()) {
v = q.poll();
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (adjArray[v][i] == 1 && !visited[i]) {
q.add(i);
visited[i] = true;
}
}
}
}
}
