그래프 순회(DFS, BFS)

1. 그래프 순회

📝 그래프 순회란 비선형 구조인 그래프로 표현된 모든 정점을 빠짐없이 탐색하는 것을 의미한다.
주요 그래프 순회 알고리즘에는 DFS와 BFS가 있다.

---

2. DFS와 BFS

☑️ 깊이 우선 탐색(Depth First Search)

• 개념: 시작 정점에서 한 방향으로 갈 수 있는 경로가 더 이상 없을 때까지 깊게 탐색하고, 마지막에 만났던 갈림길로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법이다.
• 구현 방법: 재귀함수(recursive function), 스택(Stack)

☑️ 너비 우선 탐색(Breadth First Search)

• 개념: 시작 정점의 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 순회 방법이다. 가중치가 없는 그래프에서 최단경로를 구할 때 사용할 수 있다.
• 구현 방법: 큐(Queue)

---

3. 실습 코드

📌 문제: 백준 1260. DFS와 BFS

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

public class Main {

	static int N;
	static int[][] graph;
	static boolean[] dfs_visited;
	static boolean[] bfs_visited;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st=new StringTokenizer(in.readLine()," ");
    	
    	N=Integer.parseInt(st.nextToken()); 		// 정점의 개수
    	int M=Integer.parseInt(st.nextToken()); 	// 간선의 개수
    	int V=Integer.parseInt(st.nextToken());		// 시작할 정점의 번호
    	
    	graph=new int[N+1][N+1];
    	dfs_visited=new boolean[N+1];
    	bfs_visited=new boolean[N+1];
    	
    	for(int i=0;i<M;i++) {
    		st=new StringTokenizer(in.readLine()," ");
    		int from=Integer.parseInt(st.nextToken());
    		int to=Integer.parseInt(st.nextToken());
    		graph[from][to]=graph[to][from]=1;
    	}
    	dfs(V);
    	System.out.println();
    	bfs(V);
    }
    
    static void dfs(int v) {
    	dfs_visited[v]=true;
    	System.out.print(v+" ");
    	
    	for(int i=1;i<=N;i++) {
    		if(graph[v][i]==1 && !dfs_visited[i]) {
    			dfs(i);
    		}
    	}
    	
    }
    
    static void bfs(int v) {
    	Queue<Integer> queue=new ArrayDeque<>();
    	queue.offer(v);
    	bfs_visited[v]=true;
    	
    	while(!queue.isEmpty()) {
    		int temp=queue.poll();
    		System.out.print(temp+" ");
    		for(int i=1;i<=N;i++) {
    			if(graph[temp][i]==1 && !bfs_visited[i]) {
    				queue.offer(i);
    				bfs_visited[i]=true;
    			}
    		}
    	}
    }
}