그래프 탐색 (DFS/BFS)

1. DFS

• 그래프의 깊은 부분을 우선적으로 탐색하는 방법
• 탐색을 시작한 정점에서 출발하여, 한 방향으로 갈 수 있는 경로가 끝날 때 까지 깊게 탐색하고, 더 이상 탐색할 곳이 없으면 마지막에 통과한 정점으로 되돌아가 다른 방향의 정점을 탐색
• 이 과정을 모든 정점을 방문할 때까지 반복

2. BFS

• 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문하는 방법
• 시작 정점으로부터 각 정점까지의 최단 경로를 찾는 데 사용됨
• 큐(Queue)를 사용하여 구현

3. 코드

import java.util.*;

public class GraphTest {

	static List<Integer> graph[];
	static boolean visited[];

	public static void main(String args[]) {
		graph = new ArrayList[4];
		for (int i = 0; i < 4; i++) {
			graph[i] = new ArrayList<>();
		}
		visited = new boolean[4];

		graph[0].add(1);
		graph[0].add(2);
		graph[1].add(2);
		graph[2].add(3);

		DFS(2);
		BFS(2);
	}

	private static void DFS(int vertex) {
		visited[vertex] = true;
		System.out.print(vertex + " ");

		Iterator<Integer> ite = graph[vertex].listIterator();
		while (ite.hasNext()) {
			int adj = ite.next();
			if (!visited[adj])
				DFS(adj);
		}
	}

	private static void BFS(int startVertex) {
		boolean[] visited = new boolean[graph.length];
		Queue<Integer> queue = new LinkedList<>();

		visited[startVertex] = true;
		queue.add(startVertex);

		while (!queue.isEmpty()) {
			int vertex = queue.poll();
			System.out.print(vertex + " ");

			for (int adjVertex : graph[vertex]) {
				if (!visited[adjVertex]) {
					visited[adjVertex] = true;
					queue.add(adjVertex);
				}
			}
		}
	}

}