그래프 순회 방법 중 하나중 하나이다.
그래프 탐색이란
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문한다
DFS는 깊이 우선 탐색
시작 노드에세 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드가 돌아가서, 다시 깊이 우선 탐색을 반복하게 된다.
다음과 같은 상황에서 노드가 존재할 때, 노드에서 깊이 우선 탐색에 의해 0번 -> 1번 -> 3번 -> 4번 -> 2번 순으로 노드를 찾아가며 탐색하는 방법이다.
DFS의 장단점
DFS의 장점:
1. DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비하여 메모리 공간을 덜 사용한다.
2. DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
3. DFS를 사용하여 그래프에서 순환을 감지할 수 있다.
4. 최소 실행시간에 적합하다
DFS의 단점:
1. 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
2. DFS는 두 정점 사이의 최단 경로를 찾을 때 효율적인 알고리즘이 아닐 수 있다.
DFS 구현
반복 구현 (Stack)
반복구현은 스택 구조를 사용하여 노드를 체크한다.
임의의 정점을 기준으로 하여 방문한 노드를 표시하고 스택에 푸시한다.
스택에 front에 푸시된 정점을 pop한다
방문하지 않은 모든 인접 정점을 방문한 것으로 표시하고 스택으로 표시한다
스택이 isEmpty 상태일때까지 while문을 반복하고 종료한다.
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
#define Max_N 10
int N, E;
int Graph[Max_N][Max_N];
int main()
{
cin >> N >> E;
memset(Graph, 0, sizeof(Graph));
for (int i = 0; i < E; i++) // 간선의 수만큼 반복.
{
int u, v;
cin >> u >> v;
Graph[u][v] = Graph[v][u] = 1; // 방향성 존재 X.
}
dfs(0);
return 0;
}
void dfs(int node)
{
bool visited[Max_N] = { false };
stack<int> mystack;
mystack.push(node);
while (!mystack.empty())
{
int curr = mystack.top();
mystack.pop();
if (visited[curr]) continue;
visited[curr] = true;
cout << curr << ' ';
for (int next = 0; next < N; next++)
{
if (!visited[next] && Graph[curr][next])
{
mystack.push(next);
}
}
}
}
재귀 호출
재귀 호출은 그래프의 모든 노드를 방문한다.
이 함수는 현재 정점과 방문한 집합을 입력으로 사용하고 아직 방문하지 않은 모든 인접 노드에 DFS를 적용한다.
재귀 함수 호출은 모든 노드를 방문하는 사례에서 유용하다.
#include <iostream>
#include <cstring>
using namespace std;
#define Max_N 10
int N, E;
int Graph[Max_N][Max_N];
bool visited[Max_N]; // 전역변수 설정으로 Overflow 방지.
int main()
{
cin >> N >> E;
memset(visited, 0, sizeof(visited)); // bool 값에 할당된 메모리의 크기만큼 0으로 초기화.
memset(Graph, 0, sizeof(Graph));
for (int i = 0; i < E; i++) // 간선의 수만큼 반복.
{
int u, v;
cin >> u >> v;
Graph[u][v] = Graph[v][u] = 1; // 방향성 존재 X.
}
dfs(0);
return 0;
}
void dfs(int node)
{
visited[node] = true;
cout << node << ' ';
for (int next = 0; next < N; ++next)
{
if (!visited[next] && Graph[node][next])
dfs(next);
}
}