그래프 탐색

DFS

그래프를 탐색할 때 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다.

검색 속도가 BFS에 비해 느리지만 더 간단하게 구현할 수 있다.

재귀를 이용하여 구현한다.

DFS 구현

static ArrayList<ArrayList<Integer>> adj;
static boolean[] visited;

void dfs(int x) {
	visited[x] = true;
	for(int nx : adj.get(x)) {
		if(visited[nx])
			continue;
		dfs(nx);
	}
}

BFS

그래프를 탐색할 때 시작 노드에서 탐색을 시작하여 인접 노드를 모두 탐색하고 다음 노드를 탐색하는 방법이다.

큐를 이용하여 구현한다.

가중치가 없는 그래프의 최단거리를 구하는 문제에 사용할 수 있다.

BFS 구현

static ArrayList<ArrayList<Integer>> adj;
static int[] visited;

void bfs(int x) {
	Queue<Integer> q = new LinkedList<>();
	q.add(x);
	visited[x] = 1;
	while (!q.isEmpty()) {
		x = q.poll();
		for (int nx : adj.get(x)) {
			if (visited[nx] >= 1)
				continue;
			q.add(nx);
			visited[nx] = visited[x] + 1;
		}
	}
}