[기초] C++ 깊이 우선 탐색 (Depth-First Search, DFS)

---

 

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 탐색 알고리즘 중 하나로,

시작 노드에서 출발하여 한 방향으로 갈 수 있는 끝까지 탐색한 후,

다른 방향으로 탐색하는 방식입니다.

스택을 사용하여 구현할 수 있으며, 재귀 호출을 통해 쉽게 구현할 수 있습니다.

 

---

 

탐색 방법 설명

 

• 시작 노드 선택
  탐색을 시작할 노드를 선택합니다.
  
  
• 노드 방문
  현재 노드를 방문하고, 방문했음을 표시합니다.
  
  
• 인접 노드 탐색
  방문한 노드와 인접한 노드들을 차례로 방문하지 않은 노드가 있다면,
  그 노드를 새로운 시작 노드로 선택하여 다시 방문합니다.
  
  
• 반복
  더 이상 방문할 노드가 없을 때까지 2번과 3번 과정을 반복합니다.

 

#include <iostream>
#define MAX 100

using namespace std;

// 그래프 클래스 정의
class Graph {
    int V; // 정점의 개수
    int adj[MAX][MAX]; // 인접 행렬

public:
    // 생성자
    Graph(int V);
    // 간선 추가
    void addEdge(int v, int w);
    // DFS 탐색
    void DFS(int v);
    // DFS 탐색을 위한 헬퍼 함수
    void DFSUtil(int v, bool visited[]);
};

// 그래프 생성자
Graph::Graph(int V) {
    this->V = V;
    // 인접 행렬 초기화
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            adj[i][j] = 0;
}

// 간선 추가 함수
void Graph::addEdge(int v, int w) {
    adj[v][w] = 1; // v 정점에서 w 정점으로의 간선을 추가
    adj[w][v] = 1; // 무방향 그래프의 경우 w 정점에서 v 정점으로의 간선도 추가
}

// DFS 탐색을 위한 헬퍼 함수
void Graph::DFSUtil(int v, bool visited[]) {
    // 현재 노드를 방문함으로 표시하고 출력
    visited[v] = true;
    cout << v << " ";

    // 현재 노드와 인접한 모든 노드를 탐색
    for (int i = 0; i < V; i++) {
        if (adj[v][i] && !visited[i]) {
            DFSUtil(i, visited);
        }
    }
}

// DFS 탐색 함수
void Graph::DFS(int v) {
    // 방문 여부를 체크하기 위한 배열 초기화
    bool visited[MAX] = {false};

    // 헬퍼 함수 호출하여 DFS 탐색 시작
    DFSUtil(v, visited);
}

// 메인 함수
int main() {
    // 그래프 생성 (정점의 개수: 4)
    Graph g(4);
    // 간선 추가
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    // DFS 탐색 시작 (정점 2에서 시작)
    cout << "Depth First Traversal starting from vertex 2: ";
    g.DFS(2);

    return 0;
}

 

코드 설명

 

• Graph 클래스
  그래프를 표현하는 클래스입니다.
  정점의 개수와 인접 행렬을 멤버로 갖습니다.
  
  
• addEdge 함수
  두 정점 사이에 간선을 추가합니다.
  무방향 그래프이므로 양방향으로 간선을 추가합니다.
  
  
• DFS 함수
  주어진 정점에서 DFS를 시작합니다.
  방문 여부를 기록하는 배열을 초기화하고, 'DFSUtil' 헬퍼 함수를 호출합니다.
  
  
• DFSUtil 함수
  실제 DFS 탐색을 수행하는 재귀 함수입니다.
  현재 노드를 방문하고, 인접한 노드 중 방문하지 않은 노드를 재귀적으로 방문합니다.
  
  

출력

 

Depth First Traversal starting from vertex 2: 2 0 1 3

 

프로세스 설명

 

• 탐색을 2번 정점에서 시작합니다.
  
  
• 2번 정점에 인접한 0번 정점을 방문합니다.
  
  
• 0번 정점에 인접한 1번 정점을 방문합니다.
  
  
• 1번 정점에 인접한 2번 정점은 이미 방문했으므로 건너뜁니다.
  
  
• 2번 정점에 인접한 3번 정점을 방문합니다.
  
  
• 3번 정점에 인접한 3번 정점은 이미 방문했으므로 탐색이 종료됩니다.
  
  
  

마무리

 

이 예제는 정점의 개수가 고정된 상황에서 작동하며,

인접 행렬을 사용하여 간선 정보를 저장합니다.

배열을 사용하여 메모리 사용을 줄이는 대신,

정점의 개수가 많을 경우 인접 행렬의 크기가 커질 수 있습니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀