[알고리즘] DFS와 BFS

📌 자료구조

---

해당 게시물은 자료구조-그래프에 대한 이해가 필요한 게시물입니다.
그래프

📌 그래프 순회 ( Graph traversal )

---

그래프 순회 방식에는 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)이 있다. 그래프를 순회한다는 것은 정점 하나로 부터 시작하여 정해진 규칙에 따라 모든 정점들을 한 번씩 방문하는 것을 의미한다.

📌 DFS(깊이 우선 탐색)

---

깊이 우선 탐색이란, 시작점인 정점으로부터 최대한 먼 곳으로 이동후에 더 이상 이동할 수 없는 경우 다음 갈래로 이동하는 방법이다. 해당 분기를 완벽하고 탐색하고 다음 분기로 넘어가는 것을 의미한다.

모든 정점을 방문하는 경우에 사용한다.
너비 우선 탐색에 비해 구현이 간단하다.

DFS 구현

vector<int> graph[n];
bool visit[n];

void DFS(int start)
{
	visit[start] = true;

	for (int i = 0; i < graph[start].size(); i++)
	{
		if (visit[graph[start][i]] == false)
			DFS(graph[start][i]);
	}
}

📌 BFS(너비 우선 탐색)

---

너비 우선 탐색이란, 시작점인 정점에서 최대한 넓게 이동하고, 더 이상 이동할 수 없는 경우에 더 멀리 떨어진 정점으로 이동한다.

모든 정점을 방문하는 경우에 사용한다.
두 정점사이의 최단 경로를 찾고자 할 때 사용한다.

BFS 구현

queue<int> q;
vector<int> graph[n];
bool visit[n];

void BFS(int start)
{
	visit[start] = true;
	q.push(start);

	while (!q.empty())
	{
		start = q.front();
		q.pop();

		for (int i = 0; i < graph[start].size(); i++)
		{
			if (visit[graph[start][i]] == false)
			{
				visit[graph[start][i]] = true;
				q.push(graph[start][i]);
			}
		}
	}
}

📌 그래프 순회 알고리즘 시간복잡도와 활용

---

두 방법 모두 그래프 내의 모든 정점을 방분한다는 점에서 시간복잡도는 동일하다. N이 그래프의 정점의 개수, E가 정점을 연결하는 간선의 개수라고 했을 때, 그래프를 인접 리스트 방식으로 구현한다면 DFS와 BFS의 시간복잡도는 O(N+E)이다.

DFS와 BFS의 시간복잡도 : O(N+E)

• 그래프의 모든 정점을 방문해야 할 때
  DFS와 BFS 방식 모두 그래프 내의 정점을 방문하기 때문에, 두 가지 모두 동일하게 사용가능하다.

• 최단거리를 구해야 할 때
  BFS는 시작점으로 부터 가까운 곳부터 탐색하기 때문에 BFS를 사용한다.