DFS와 BFS

깊이 우선 탐색(Depth First Search)

• 재귀를 사용한다. Stack으로 구현

void dfs(int x) {
	// x를 방문했다.
	visit[x] = true;
	
	// x에서 갈 수 있는 곳들을 모두 방문한다.
	for (int y : x에서 갈 수 있는 점들) {
		if (visit[y]) // y를 이미 갈 수 있는 사실을 안다면 갈 필요가 없다.
			continue;
	
		// y에서 갈 수 있는 곳들을 탐색
		dfs(y);
	}
}

시간 복잡도 :

• 인접 행렬 : DFS 하나에 for loop를 V만큼 돌기 때문에, O(V) 시간이 필요하다. 정점을 방문 할때마다 DFS를 호출하는데, V개의 정점을 탐색하기 때문에 DFS의 전체 시간복잡도는 = V * O(V) = O(V^2)

• 인접 리스트 :

  DFS의 호출은 총 V번이다. 인접 리스트는 정점에 연결 되어있는 간선 개수만큼 탐색을 하기 때문에 모든 DFS 호출 시간이 동일하지 않다.

  정점 방문 : 모든 정점을 한 번씩 방문해야 하므로 총 O(V) 시간이 소요된다.

  간선 방문 : 각 간선은 한 번씩만 탐색되므로 O(E) 시간이 소요된다.

  따라서 인접 리스트의 시간 복잡도는 O(V+E)가 된다. 이는 정점, 간선 개수에 비례하는 선형 시간 복잡도를 가진다.

너비 우선 탐색(Breadth First Search)

• 큐를 사용한다.

  • queue에 정점이 남았다 → 아직 방문 가능한 점이 존재한다, 탐색 중(while)이다.

  • queue가 비어있다. → 시작점에서 갈 수 있는 모든 점을 찾았다. 탐색이 끝났다.

void bfs(int start) {
	Queue<Integer> queue = new LinkedList<>();
	
	// start는 방문 가능한 점이므로 queue에 넣고 시작한다.
	queue.offer(start);
	visit[start] = true;   // start는 탐색 했다고 표시 (중요!!)
	
	while (!queue.isEmpty()) // 더 방문할 점이 없다면 정지
		int x = queue.poll();
	
		for (int y : x에서 갈 수 있는 점들) {
			if (visit[y]) continue;
			
			// y를 갈 수 있으니까 queue에 추가하고, visit 처리
			queue.offer(y);
			visit[y] = true;
}

시간 복잡도 :

• 인접 행렬 : 정점 하나당 for loop의 시간 복잡도를 가지므로 모든 정점은 O(V)의 시간이 걸린다. 그리고 이 안에서 while loop를 V번 반복 실행한다. 따라서 시간 복잡도는 O(V^2)이 된다.

• 인접 리스트 : 그래프 초기화는 O(V)가 걸리고, 데이터는 추가는 O(1)만큼 소요된다. 하지만 이건 무시 해도된다. 정점 방문 : 각 정점을 큐에 넣을 때 방문하게 된다. 정점은 한 번씩마느 방문하므로 O(V) 시간이 필요하다. 간선 방문 : 간선을 탐색할 때마다 해당 간선의 연결된 정점을 큐에 삽입한다. 간선은 한번 방문하므로 O(E) 따라서 인접 리스트로 구현한 전체 시간 복잡도는 O(V+E)가 된다. 정점과 간선 수에 비례하여 선형 시간 복잡도를 가지고있다.