DFS (Depth First Search)

DFS(깊이 우선 탐색)란 그래프를 탐색하는 방법 중 하나로 현재 정점으로부터 갈 수 있는 만큼 최대한 깊이 탐색하고, 더 이상 탐색할 곳이 없으면 이전 정점으로 돌아가는 알고리즘이다.

DFS 특징

<aside> 💡

복잡도 (정점 수 : V , 간선 수 : E)

</aside>

• 시간 복잡도 (인접 리스트) : O(V + E)
• 시간 복잡도 (인접 행렬) : O(V^2)
• 공간 복잡도 : O(V)

<aside> 💡

장점

</aside>

• 재귀 함수로 구현시 별도의 자료구조가 필요하지 않아 메모리를 아낄 수 있다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

<aside> 💡

단점

</aside>

• 목표에 도달할 수 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
• 얻은 결과가 최단 경로라는 보장이 없다.
• 깊이가 무한히 깊어지면 스택오버플로우가 발생할 수 있다.

DFS 구현

stack 또는 재귀 함수를 이용해 구현할 수 있다.

1. 탐색 시작 노드를 stack 에 삽입하고 방문 처리한다.
2. stack 의 상단 노드의 인접 노드 중 방문하지 않은 노드가 있으면 stack 에 삽입 후 방문 처리한다. 방문하지 않은 노드가 없으면 stack 의 상단 노드를 제거한다.
3. 2번 과정을 반복하다 stack 이 비게되면 탐색을 종료한다.

초기 그래프 및 간선 정보

시작 노드 stack에 삽입 및 방문 처리

1번 노드와 인접한 노드 탐색, 방문 여부 확인 후 stack에 삽입 및 방문 처리

2번 노드와 인접한 노드 탐색, 방문 여부 확인 후 stack에 삽입 및 방문 처리

4번 노드와 인접한 노드 탐색, 방문 안한 노드가 없으므로 stack에서 제거

2번 노드와 인접한 노드 탐색, 방문 여부 확인 후 stack에 삽입 및 방문 처리

5번 노드와 인접한 노드 탐색, 방문 여부 확인 후 stack에 삽입 및 방문 처리

6, 5, 2번 노드와 인접한 노드 탐색, 방문 안한 노드가 없으므로 stack에서 제거

1번 노드와 인접한 노드 탐색, 방문 여부 확인 후 stack에 삽입 및 방문 처리

3, 1번 노드와 인접한 노드 탐색, 모든 노드 탐색 후 stack이 비었으므로 탐색 종료

DFS 코드

• 인접 리스트를 이용해 구현하기

std::vector<std::vector<int>> Graph; // 인접 리스트로 구현된 그래프
std::vector<bool> bVisited; // 방문 여부

void DFS(int Start)
{
	std::stack<int> S; // 스택 이용

	int Now = Start;
	bVisited[Now] = true;
	S.push(Now);

	while (!S.empty())
	{
		Now = S.top();
		bool isVisited = false;

		for (int i = 0; i < static_cast<int>(Graph[Now].size()); ++i)
		{
			int Next = Graph[Now][i];
			if (!bVisited[Next])
			{
				S.push(Next);
				bVisited[Next] = true;
				isVisited = true;
				break;
			}
		}

		// 더 이상 방문할 곳이 없으면
		if (!isVisited)
		{
			S.pop();
		}
	}
}

• 인접 행렬을 이용해 구현하기

std::vector<std::vector<int>> Graph; // 인접 행렬로 구현된 그래프
std::vector<bool> bVisited; // 방문 여부

void DFS(int Start)
{
	int Now = Start;
	bVisited[Now] = true;

	for (int i = 0; i < static_cast<int>(Graph.size()); ++i)
	{
		if (0 == Graph[Now][i])
		{
			continue;
		}

		if (!bVisited[i])
		{
			DFS(i); // 재귀 함수 이용
		}
	}
}

아래의 코드는 다음 그래프를 BFS를 통해 노드들을 탐색하고, 방문한 노드를 출력하는 코드입니다.

#include <iostream>
#include <vector>
#include <stack>

int main()
{
	std::vector<std::vector<int>> Graph(7, std::vector<int>(0, 0));
	std::vector<bool> bVisited(7, 0);

	// 인접 리스트 그래프 생성
	Graph[1].push_back(2);
	Graph[1].push_back(3);

	Graph[2].push_back(1);
	Graph[2].push_back(4);
	Graph[2].push_back(5);

	Graph[3].push_back(1);

	Graph[4].push_back(2);

	Graph[5].push_back(2);
	Graph[5].push_back(6);

	Graph[6].push_back(5);

	// DFS
	std::stack<int> S;

	int Now = 1;
	S.push(Now);
	bVisited[Now] = true;
	std::cout << "방문 노드 : " << Now << std::endl;

	while (!S.empty())
	{
		Now = S.top();
		bool isVisited = false;

		for (int i = 0; i < static_cast<int>(Graph[Now].size()); ++i)
		{
			int Next = Graph[Now][i];
			if (!bVisited[Next])
			{
				std::cout << "방문 노드 : " << Next << std::endl;
				S.push(Next);
				bVisited[Next] = true;
				isVisited = true;
				break;
			}
		}

		if (!isVisited)
		{
			S.pop();
		}
	}

	return 0;
}

방문 노드 : 1
방문 노드 : 2
방문 노드 : 4
방문 노드 : 5
방문 노드 : 6
방문 노드 : 3