Algorithm 14일차

알고리즘에서 그래프를 bfs로 완전 탐색할 수 있다.

그래프에서 bfs는 아래와 같이 진행된다.

1. 시작 정점을 큐에 삽입한다.
2. 시작 정점을 방문한 것으로 표시한다.
3. 큐의 첫 번째 원소를 반환한다.
4. 반환한 원소에 연결된 모든 간선에 대해 인접 정점을 검사한다.
   이 때, 인접 정점이 방문하지 않은 곳이라면 해당 정점을 큐에 넣고, 방문한 것으로 표시한다.
5. 3, 4 과정을 큐가 빌 때까지 반복한다.

알고리즘에서 인접 행렬을 bfs로 완전 탐색할 수 있다.

아래와 같은 그래프가 있다.

위 그래프가 인접 행렬로 표현되어 있을 때, bfs로 완전 탐색하는 코드는 아래와 같다.

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

public class MatrixBFS {
	static int[][] adjMatrix;
	static int V;
	
	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();
			
			for (int i = 0; i < V; i++) {
				if (adjMatrix[current][i] != 0 && !visited[i]) { // 인접했는지, 이전에 방문하지 않았는지 확인
					queue.offer(i);
					visited[i] = true;
				}
			}
			
			System.out.print((char)(current + 65) + " ");
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		int E = sc.nextInt();
		
		adjMatrix = new int[V][V];
		
		int from, to;
		
		for (int i = 0; i < E; i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			
			adjMatrix[from][to] = adjMatrix[to][from] = 1;
		}
		
		bfs(0);
		
		sc.close();
	}
}

입력값과 출력 결과는 아래와 같다.

1. 입력값
   7
   8
   0 1
   0 2
   1 3
   1 4
   3 5
   4 5
   5 6
   2 6

2. 출력 결과
   A B C D E G F

알고리즘에서 인접 리스트를 bfs로 완전 탐색할 수 있다.

위 그래프가 Node 클래스를 직접 구현한 인접 리스트로 표현되어 있을 때,
bfs로 완전 탐색하는 코드는 아래와 같다.

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

public class ListBFS {
	static Node[] adjList;
	static int V;
	
	static class Node {
		int V;
		Node node;
		
		public Node(int v, Node node) {
			super();
			V = v;
			this.node = node;
		}
		
		@Override
		public String toString() {
			return "Node [V=" + V + ", node=" + node + "]";
		}
	}
	
	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();
			
			for (Node temp = adjList[current]; temp != null; temp = temp.node) {
				if (!visited[temp.V]) { // 이전에 방문했는지 확인
					queue.offer(temp.V);
					visited[temp.V] = true;
				}
			}
			
			System.out.print((char)(current + 65) + " ");
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		int E = sc.nextInt();
		
		adjList = new Node[V];
		
		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);
		
		sc.close();
	}
}

입력값과 출력 결과는 아래와 같다.

1. 입력값
   7
   8
   0 1
   0 2
   1 3
   1 4
   3 5
   4 5
   5 6
   2 6

2. 출력 결과
   A C B G E D F

위 그래프가 List를 이용한 인접 리스트로 표현되어 있을 때,
bfs로 완전 탐색하는 코드는 아래와 같다.

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

public class ListBFS2 {
	static List<Integer>[] adjList;
	static int V;
	
	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();
			
			for (int V : adjList[current]) {
				if (!visited[V]) { // 이전에 방문했는지 확인
					queue.offer(V);
					visited[V] = true;
				}
			}
			
			System.out.print((char)(current + 65) + " ");
		}
	}
	
	public static void main(String[] args) {	
		Scanner sc = new Scanner(System.in);
		
		V = sc.nextInt();
		int E = sc.nextInt();
		
		adjList = new ArrayList[V];
		
		for (int i = 0; i < V; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		
		int from, to;
		
		for (int i = 0; i < E; i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			
			adjList[from].add(to);
			adjList[to].add(from);
		}
		
		bfs(0);
		
		sc.close();
	}
}

입력값과 출력 결과는 아래와 같다.

1. 입력값
   7
   8
   0 1
   0 2
   1 3
   1 4
   3 5
   4 5
   5 6
   2 6

2. 출력 결과
   A B C D E G F