BFS(너비우선탐색)

[광고 누르면 오늘의 행운 상승!!]

• 그래프를 탐색하는 방법에는 크게 두 가지가 있다.
  - 깊이 우선 탐색(Depth First Search)
  - 너비 우선 탐색(Breadth First Search)
  
  
• 너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에,
  방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
  
  
• 인접한 정점들에 대한 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로,
  선입선출 형태의 자료구조인 큐를 활용함.
  
  
• 최단경로 구하기, 동시에 퍼져나가기(가중치가 1일때) 문제에서 사용한다.

DFS(Queue)

package BFS;

import java.io.*;
import java.util.*;

public class BfsTest1 {

	public static int V,E;
	public static int[][] graph;
	public static boolean[] visit;
	public static Queue<Integer> queue;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_bfs.txt"));
		Scanner sc=  new Scanner(System.in);

		V = sc.nextInt();
		E = sc.nextInt();
		
		graph = new int[V][V];
		queue = new LinkedList<Integer>();
		
		for(int i =0; i < E ; i++) {
			int v = sc.nextInt();
			int u = sc.nextInt();
			graph[v][u] = graph[u][v] =  1;
			
		}
		
		//visit = new boolean[V];
		bfs(0);
		
		sc.close();
	}

	public static void bfs(int node) {
		visit = new boolean[V];
		Queue<Integer> q = new LinkedList<>();
		q.add(node);
		visit[node] = true;
		while (!q.isEmpty()) {
			node = q.remove();
			System.out.print(node + " ");
			for (int next = 0; next < V; next++) {
				if (!visit[next] && graph[node][next] == 1) {
					q.add(next);
					visit[next] = true;
				}
			}
		}
		System.out.println();
	}
}