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

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

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
  ex) 모든 도시를 통하는 여행 경로, 특정 도시에서 다른 도시로 갈 수 있는지 여부

• 그래프 탐색법 중 하나인 DFS는 다음 분기로 넘어가기 전에 해당 분기를 끝마치는 탐색법이다.

• 경로 탐색 시 이어지는 길이 있으면 끝까지 간다.

• 방문여부를 반드시 검사하여 무한루프의 위험을 피해야 한다.

// 순환 호출을 이용한 DFS

void Dfs(int here)
{

	// 방문!
	visited[here] = true;
    
	cout <<"Visited: "<< here << endl;
    
	for (int there : adjacent[here])
	{
    	// 인접한 정점이 아직 방문하지 않은 정점일 경우
		if (visited[there] == false)
			Dfs(there);	// 방문 실행
	}
}

void DfsAll()
{
	visited = vector<bool>(6, false);

	// 서로 연결이 되지 않은 노드가 있을 수 있으므로
	for (int i = 0;i < 6;i++)
		if (visited[i] == false)
			Dfs(i);
}

• 그래프 탐색은 모든 정점을 방문하는 것을 목표로 하므로 방문 여부를 확인하는 bool변수를 생성해 방문 시 체크해준다.

• 재귀를 사용하여 현재 정점과 연결되어 있는 모든 정점을 탐색해 방문을 실행한다.

• DFS는 그래프(정점의 수:N, 간선의 수:E)의 모든 간선을 조회한다.

  • 인접 리스트로 표현된 그래프: O(N+E)
  • 인접 행렬로 표현된 그래프: O(N^2)

• 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.