깊이우선탐색 DFS

Description

깊이우선탐색 DFS(Depth First Search)는 깊이를 우선적으로하여 탐색하는 알고리즘이다.
BFS에서는 Queue가 사용되었다면 DFS에서는 Stack을 사용한다.

이러한 그래프 구조의 노드들이 있다고 보자.

DFS는 맨 처음 시작 노드를 스택에 삽입하면서 시작한다. 그리고 방문처리를 해준다.
그래서 1부터 시작하여 스택에 1이 쌓인다.
그리고 다음 노드로 향하는 간선을 선택한다. (1 -> 2)

2를 방문하여 스택에 2가 쌓인다.
다음 노드로 향하는 간선 2 -> 3 을 찾는다.

3을 방문하고 스택에 3이 쌓인다.
다음 노드로 향하는 간선 3 -> 4 를 찾는다.

다음 간선은 4 -> 1 이나 1은 이미 방문하였던 노등기 때문에 끝에 도달하게되어 다시 되돌아간다.
이때 스택에서 해당 노드인 4를 빼고 돌아간다.

3으로 되돌아 왔지만 다음 간선이 존재하지 않기 때문에 스택에서 3을 빼며 2로 되돌아간다.

2도 마찬가지로 다음 간선이 없기 때문에 스택에서 2를 빼며 1로 돌아간다.

다시 노드 1로 돌아왔다.
다음 간선으로는 4와 6이 있지만 4는 이미 방문하였기 때문에 6으로 가는 간선을 선택한다.

6을 방문하고 스택에 6이 쌓인다.
다음 노드로 향하는 간선 6 -> 5를 찾는다.

5를 방문하고 스택에 5가 쌓인다.
이로써 모든 노드를 방문하게 되었고 더이상 갈 수 있는 노드가 없어 뒤로 돌아가 dfs를 종료하게 된다.
방문의 순서는 1 -> 2 -> 3 -> 4 -> 6 -> 5 가 된다.

---

Cord

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[7];
bool visited[7];

void dfs(int _start)
{
	visited[_start] = true;
	cout << _start << ' ';

	// v[_start]가 가진 간선의 수 만큼 방문 시도 
	for (int i = 0; i < v[_start].size(); i++)
	{
		int next = v[_start][i];

		if (!visited[next])
		{
			dfs(next);
		}
	}
}

int main()
{
	// 간선 연결
	// 1 <-> 2
	v[1].push_back(2);
	v[2].push_back(1);
	// 1 <-> 4
	v[1].push_back(4);
	v[4].push_back(1);
	// 1 <-> 6
	v[1].push_back(6);
	v[6].push_back(1);
	// 2 <-> 3
	v[2].push_back(3);
	v[3].push_back(2);
	// 3 <-> 4
	v[3].push_back(4);
	v[4].push_back(3);
	// 5 <-> 6
	v[5].push_back(6);
	v[6].push_back(5);

    // dfs 실행
	dfs(1);

	return 0;
}

---

Result