[알고리즘] Graph - 깊이 우선 탐색 DFS (Depth First Search)

깊이 우선 탐색(Depth First Search)

그래프 탐색 알고리즘 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하며 깊이를 우선으로 탐색하는 알고리즘 입니다.

• 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게되면 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 과정
• 넓게 탐색하기 전에 깊게 탐색
• 모든 노드를 방문하고 싶을 때 사용한다.
• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 어떤 노드를 방문했었는지 여부를 검사해야 한다.
• O(V + E) V(노드의 수), E(간선의 수)

 

 

DFS 탐색 과정

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html#google_vignette

 

• 시작 노드를 선택한다.
• 현재 노드를 방문한다.
  • 방문한 노드를 방문했다고 표시한다.
• 현재 노드의 인접 노드를 탐색한다.
  • 인접 노드가 없는 경우 탐색을 종료한다.
  • 깊이를 우선으로 탐색한다.
• 모든 인접 노드 방문 후, 이전 노드로 되돌아간다.
  • 현재 노드의 인접 노드가 모두 방문 했거나, 방문할 노드가 없다면 이전 노드로 되돌아가며 탐색한다.
• 탐색 종료

 

 

구현 예시 코드

struct Vertex
{
    // Data
};

vector<Vertex> vertices;
vector<vector<int>> adjacencyList;
vector<bool> visited; 

// DFS 함수 (재귀)
void DFS(int current) {
    visited[current] = true;
    cout << "Visited : " << current << endl;

    // 모든 인접 정점들을 순회
    for (int i = 0; i < adjacencyList[current].size(); i++)
    {
        int next = adjacencyList[current][i];
        if (!visited[next])
        {
            DFS(next);
        }
    }

}

// 끊겨있던 노드들 순회
void DFSAll()
{
    for (int i = 0; i < 6; i++)
    {
        if (visited[i] == false)
        {
            DFS(i);
        }
    }
}

void CreateGraph()
{
    vertices.resize(5);
    adjacencyList = vector<vector<int>>(5);
    visited = vector<bool>(5, false);

    adjacencyList[0].push_back(1);
    adjacencyList[0].push_back(3);
    adjacencyList[1].push_back(0);
    adjacencyList[1].push_back(2);
    adjacencyList[2].push_back(1);
    adjacencyList[2].push_back(3);
    adjacencyList[2].push_back(4);
    adjacencyList[3].push_back(2);
    adjacencyList[3].push_back(4);
    adjacencyList[4].push_back(2);
    adjacencyList[4].push_back(0);
}

출력 결과