DFS와 BFS

DFS와 BFS

출처 - https://hudi.blog/dfs-bfs/

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

DFS 개념

• DFS는 루트 노드(또는 다른 임의의 노드) 에서 시작해서 다음 분기(branch)로 넘어가기전에 해당 분기를 끝까지 탐색하는 방법이다.
• stack 또는 재귀 함수 방식을 사용해서 구현하다. (재귀 방식도 사실상 stack 방식이다.)

DFS의 특징

• 모든 노드를 방문하는 경우 사용할 수 있다.
• 경로의 특징을 저장하는경우 사용한다.(ex 깊이가 5 이상인경우를 구할떄 )
• BFS보다 간단하지만 느리다.

DFS 코드

void DFS(int n,int v) {

	if (visited[v])
		return;
	visited[v] = true; 
	cout << v << " ";
	for (int i = 1; i <= n; i++) {
		if (arr[v][i] && !visited[i]) {
			DFS(n, i);
		}
	}

}

백준 1260번 문제의 코드이다.

DFS의 기본적인 동작 과정은 다음과 같다.

• 우선 방문하는 노드의 visited값을 true로 바꿔준다.
• for문을 통해 현재 노드와 연결되어있으면서 -> arr[v][i] , 방문하지 않았으면 -> !visited[i] 해당 노드로 DFS를 다시 수행한다.
•  

BFS (Breadth First Search) 너비 우선 탐색

BFS 개념

• BFS는 루트 노드(또는 다른 임의의 노드) 에서 인접한 노드를 먼저 탐색하는 방법이다.

BFS의 특징

• 모든 노드를 방문하는 경우 사용할 수 있다.
• 주로 최단 경로를 구할때 사용한다.(ex 미로찾기)

BFS 코드

void BFS(int n,int v) {
	queue<int> que;
	que.push(v);
	visited[v] = true;

	while (!que.empty()) {
		int x = que.front();
		cout << x << " ";
		que.pop();
		for (int i = 1; i <= n; i++) {
			if (arr[x][i] && !visited[i]) {
				que.push(i);
				visited[i] = true;
			}
		}
	}
}

마찬가지로 백준 1260번 문제의 코드이다.

BFS의 기본적인 동작 과정은 다음과 같다.

• queue를 만든후 루트노드를 push한다.
• front값을 구하고 pop을 한다.
• for문을 통해 현재 노드와 연결되어있으면서 -> arr[v][i] , 방문하지 않았으면 -> !visited[i] 해당 노드를 queue에 push하고 visited값을 true로 바꿔준다.

 

정리

DFS와 BFS를 장단점, 사용시기 정리

1. 그래프의 모든 정점을 방문하는경우
   • 모든 정점을 방문해야 하기 때문에 DFS,BFS 아무거나 사용하면된다.
2. 경로의 특징을 저장해야하는 경우
   • 경로의 특징을 저장하는경우 DFS를 사용한다. 
   • 예를 들어 깊이가 5까지 들어가는 경우를 찾아야 할때, 각 정점에 어떤 값이 있고 해당 값이 중복되면 안되는경우
3. 최단 거리를 구하는경우
   • 최단거리, 최소비용 등 최소의 값을 구해야 할때 BFS를 사용한다.

 

인접행렬과 인접리스트

위에서 DFS와 BFS의 코드를 설명할때 인접 행렬을 사용했다.

하지만 그래프 탐색 문제를 풀때 인접 행렬과 인접리스트를 사용할 수 있다.

각각의 장단점이 존재한다.

https://bangbaeking.tistory.com/22

인접행렬과 인접리스트