DFS & BFS

호돌·2021년 8월 17일

CS - 알고리즘

목록 보기

8/10

DFS와 BFS

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다.

경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 된다.

DFS( 깊이 우선 탐색 , Depth-First Search)

루트 노드( 혹은 다른 임의의 노드)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색하는 방법

자기 자신을 호출하는 순한 알고리즘의 형태를 지님 (재귀 or 스택)
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것입니다. ex) visit[index] = true;
미로를 탐색할 때, 해당 분기에서 갈 수 있을때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다.
모든 노드를 방문하고자 할 때, 이 방법을 선택합니다.
너비우선탐색(BFS)보다 더 간단합니다.
검색 속도 자체는 너비우선탐색(BFS)에 비해서 느립니다.

코드

// dfs, 재귀, 인접 행렬, i 정점부터 시작한다.
public static void dfs(int i) {
	visit[i] = true;
	System.out.print(i + " ");
	for(int j=1; j<n+1; j++) {
		if(map[i][j] == 1 && visit[j] == false) {
		dfs(j);
		}
	}
}

시간 복잡도

V는 접점, E는 간선을 뜻한다.

인접 행렬 : O(V^2)
인접 리스트 : O(V+E)

BFS( 너비 우선 탐색 , Bread-First Search)

BFS는 재귀적으로 동작하지 않는다.
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.(무한루프)
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용하여 선입선출 원칙으로 탐색합니다.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것입니다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다.
- ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
- DFS의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
- BFS의 경우 - A와 가까운 관계부터 탐색한다.

코드

// bfs, q사용, 인접행렬, i 정점부터 시작한다.
public static void bfs(int i) {
	Queue<Integer> q = new LinkedList<>();
	q.offer(i);
	visit[i] = true;
	while(!q.isEmpty()) {
		int temp = q.poll();
		System.out.print(temp + " ");
		for(int j=1; j<n+1; j++) {
			if(map[temp][j] == 1 && visit[j] == false) {
			q.offer(j);
			visit[j] = true;
			}
		}
	}
}