깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) / 장단점, 구현 및 시간복잡도

DFS의 장/단점

• 장점
  • 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다.
  • 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능)

DFS의 구현

그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다.

 

인접 행렬로 구현했을 경우

 

[시간복잡도]

 DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로

n*O(n)이므로 O(n^2)의 시간복잡도를 가지게 된다.

vector<vector<int>> adjacent; //인접 행렬로 구현된 그래프 들어감
vector<bool> visited; // 그래프의 정점만큼의 크기로 생성

void DFS(int now)
{
	visited[now] = true;
	int N = adjacent.size();
	for (int i = 0; i < N; i++)
	{
		if (adjacent[now][i] == 0)
			continue;
		
		if (!visited[i])
			DFS(i);
	}
	
}

 

 

인접 리스트로 구현했을 경우

 

[시간복잡도]

 DFS가 총 N번 호출되긴 하지만 인접행렬과 달리 인접 리스트로 구현하게 되면 DFS하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되므로 예측이 불가능 하다. 하지만 DFS가 다 끝난 후를 생각하면, 모든 정점을 한번씩 다 방문하고, 모든 간선을 한번씩 모두 검사했다고 할 수 있으므로 O(n+e)의 시간이 걸렸다고 할 수 있다.

따라서 시간복잡도는 O(n+e)이다.

vector<vector<int>> adjacent; //인접 리스트로 구현된 그래프 들어감
vector<bool> visited; // 그래프의 정점만큼의 크기로 생성

void DFS(int now)
{
	visited[now] = true;

	for (int i = 0; i < adjacent[now].size(); i++)
	{
		int next = adjacent[now][i];
		if (!visited[next])
			DFS(next);
	}
	
}

BFS의 장/단점

• 장점
  • 너비를 우선으로 탐색하므로 답이 되는 경로가 여러 개인 경우에도 최단경로를 얻을 수 있다.
  • 경로가 무한히 깊어져도 최단경로를 반드시 찾을 수 잇다.
  • 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.
• 단점
  • DFS와 달리 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다.

인접 행렬로 구현했을 경우

[시간복잡도]

 정점 한개당 N번의 for loop를 돌기 때문에 O(n)의 시간이 걸리는데 이 for loop는 큐에 아무것도 없을 때까지 즉, 모든 정점을 방문할 때까지 실행되므로 n번 반복 실행된다. 따라서 시간복잡도는 O(n^2)이다.

vector<vector<int>> adjacent; //인접 행렬로 구현된 그래프 들어감
vector<bool> discovered; // 그래프의 정점만큼의 크기로 생성

void BFS(int now)
{
	queue<int> q;
	int N = adjacent.size();
	
	q.push(now);
	discovered[now] == true;
	
	while(!q.empty())
	{
		now = q.front();
		q.pop();
		
		for (int i = 0; i < N; i++)
		{
			if (adjacent[now][i] == 0)
				continue;
			
			if (!discovered[i])
			{
				q.push(i);
				discovered[i] = true;
			}
		}
	}
}

 

인접 리스트로 구현했을 경우

[시간복잡도]

 아까 리스트로 구현된 DFS와 비슷한 논리로 시간복잡도를 구할 수 있다.

BFS가 다 끝난 후를 생각해보면, 모든 간선에 대해서 한번씩 검사를 할 것이고, 각 정점을 한번씩 모두 방문하기 때문에 O(n+e)만큼의 시간복잡도를 가질 것이다.

vector<vector<int>> adjacent; //인접 리스트로 구현된 그래프 들어감
vector<bool> discovered; // 그래프의 정점만큼의 크기로 생성

void BFS(int now)
{
	queue<int> q;

	q.push(now);
	discovered[now] == true;
	
	while(!q.empty())
	{
		now = q.front();
		q.pop();
		
		for (int i = 0; i < adjacent[now].size(); i++)
		{
			int next = adjacent[now][i];
			if (!discovered[next])
			{
				q.push(next);
				discovered[next] = true;
			}
		}
	}
}

 

[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) — CULRRY (tistory.com)