DFS (깊이 우선 탐색)

DFS 기법은 Depth First Search의 줄임말로,

이름에서도 알 수 있듯 길이 있는 경우 깊이 깊이 타고 들어가는 탐색 기법이다.

 

여기서 길이 있다는 말은 지정한 버텍스에 연결된 엣지가 있다는 말로,

dfs는 방문한 버텍스에 연결된 엣지를 따라 계속해서 다른 버텍스에 진입하는 것을 의미한다.

 

따라서

1) 버텍스에 연결된 엣지를 따라 다음 버텍스 탐색

2) 방문한 버텍스가 방문한 적이 있는 경우, 다음 버텍스 탐색

두 개의 과정을 거치게 되며, 

이 과정을 재귀적 호출을 통해 구현하게 된다.

 

앞서 그래프 자료구조는 인접 리스트 혹은 인접 행렬 두가지 방법으로 구현이 가능함을 보여주었다.

따라서 DFS도 두 가지 방법을 소개해 드리려 한다.

 

인접 리스트를 활용한 방법

1. 그래프 생성

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void CreateGraph
{
    graph = vector<vector<int>>(6);
    graph[0] = { 1,3 };
    graph[1] = { 0,2,3 };
    graph[3] = { 4 };
    graph[5] = { 4 };

    visited = vector<bool>(6, false);
}

 

2. DFS 코드 작성

void DFS(int here)
{
    visited[here] = true;
    cout<<"visited : "<<here<<'\n';
    
    for(int i=0;i<graph[here].size();i++)
    {
        int target = graph[here][i]; // 연결된 vertex 값 추출
        
        if(!visited[target])
        {
            DFS(target); // 방문한 vertex에 연결된 다른 vertex 탐색 시작.
        }
    }
}

 

 

인접 행렬을 활용한 방법

1. 그래프 생성

#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool>> graph;
vector<bool> visited;

void CreateGraph
{
    graph = vector<vector<bool>>(6, vector<bool>(6,false));
    graph[0][1] = true;
    graph[0][3] = true;
    graph[1][0] = true;
    graph[1][2] = true;
    graph[1][3] = true;
    graph[3][4] = true;
    graph[5][4] = true;

    visited = vector<bool>(6, false);
}

 

2. DFS 코드 작성

void DFS(int here)
{
    visited[here] = true;
    cout<<"visited : "<<here<<'\n';
    
    for(int i=0;i<graph[here].size();i++)
    {
        if(!graph[here][i]) //연결되지 않은 vertex
            continue;
        
        if(!visited[i]) // i = here vertex에 연결된 vertex 값
            DFS(i);
    }
}

 

 

모든 vertex 탐색을 위한 코드 작성 

- 인접 리스트/ 인접 행렬 모두 동일하게 적용.

void DFS_all()
{
    for(int i=0;i<visited.size();i++)
    {
        if(!visited[i])
            DFS(i);
    }
}

 

main문 작성

int main()
{
    CreateGraph();
    DFS_all();
    return 0;
}