DFS(깊이우선 탐색)

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

-깊이를 우선적으로 추구하는 탐색

-Stack사용

-갈 수만 있다면 끝까지 깊숙히 가 보고, 거기서 길이 없다면 되돌아오는 방식

-갈 수 있는 길을 다 가보고 그래도 가는 길이 없다면 그때가서 탐색을 종료하는 소모적 탐색(Exhaustive Search)의 종류 중 하나(다른 하나는 BFS(너비우선 탐색))

-그래프 순회(Graph Traversal)방법 중 하나

 

사용하는 경우

1. 어떤 정해진 목적지를 찾는 경우

2. 주어진 그래프 내부의 모든 노드를 찾아가서 필요한 작업을 수행하게 하는 경우

 

DFS의 규칙

1.막다른 노드에 도착한 경우 막다르지 않은 길을 찾을 때까지 Backtracking(노드를 되돌아가는 행위)

-stack의 pop작업으로 수행

-Backtracking예시 ( A(출발노드)에서 F(목적지노드)까지 갈경우 )

  1. A-G-H순서대로 탐색하면서 들린 노드를 Stack에 Push

  2. H가 막다른 길이여서 막다른 길이 아닐 때까지 Backtracking하면서 Stack에서 Pop

  3. 새로운 길이 나오면 다시 Stack에 Push

 

 

 

2.어떤 길을 따라서 계속 원을 그리며 도는 경우를 막기 위해 "한번 들린 노드는 다시 안간다는 규칙을 추가" 

- 처음 들린 노드를 Stack에 Push를 할 때 들렸다는 표시를 해줌

- 새로운 노드가 나올 때 까지 Stack에서 Pop하면서 Backtracking

 

-예시(A에서 E까지 가는 경우)

 

 

3. 인접한 노드가 여럿 있을 때 어떤 노드로 먼저 가느냐에 대한 규칙

-보통, 알파벳 순서로 함 (어떤 규칙이든 일관성있게 적용하면 됨)

 

 

<코드 예시>

#include <iostream>
#include <vector>

//그래프의 인접 리스트 표현
std::vector<std::vector<int>> adj_list_graph;
//각 정점 방문 여부
std::vector<bool> visited;

void dfs(int _start_vertice)
{
	std::cout << "DFS Visits " << _start_vertice << std::endl;
	visited[_start_vertice] = true;
	//모든 인접 정점을 순회
	for (int i = 0; i < adj_list_graph[_start_vertice].size(); ++i)
	{
		int there = adj_list_graph[_start_vertice][i];
		//아직 방문안했다면 방문
		if (!visited[there])
		{
			dfs(there);
		}
	}
}
void dfsAll()
{
	visited = std::vector<bool>(adj_list_graph.size(), false);
	//모든 정점 순회하면서, 아직 방문한적 없으면 방문
	for (int i = 0; i < adj_list_graph.size(); ++i)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}
}
int main(void)
{
	int num_vertices = 5;
	adj_list_graph = std::vector<std::vector<int>>(num_vertices);
	adj_list_graph[0].push_back(1);
	adj_list_graph[0].push_back(2);
	adj_list_graph[1].push_back(3);
	adj_list_graph[1].push_back(4);
	adj_list_graph[2].push_back(0);
	adj_list_graph[3].push_back(1);
	adj_list_graph[4].push_back(1);
	dfsAll();
}