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

DFS : Depth-First Search 

깊이 우선 탐색(Depth First Search) 에 대해서 알아보겠습니다.

 

깊이 우선 검색시 방문 순서

위 그래프와 노드 번호는 깊이 우선 검색을 Root 로 부터 시작하는 경우의 방문 순서를 보여주고 있습니다.

Leaf 노드(방문하지 않은 이웃이 없는 노드)를 만나거나 목표 상태에 도달하면 이전 노드로 역추적하여 다른 방문하지 않은 분기를 탐색합니다.(Preorder)

방문하는 도중에 만나는 새로운 Node 의 하위 후손을 먼저 방문하기 위해서는 후입선출(LIFO) 처리가 필요하게 되고, 이것은 DFS 는 재귀적인 호출 또는 Stack 을 사용해서 탐색하게 됨을 의미합니다.

즉, 각 Node 를 만나서 하위 자식 Node 정보를 추가하고, 추가한 하위 자식 Node 부터 검색하는 것입니다.

 

Implementation

위에서 언급했듯이 DFS 에서는 Stack 이나 재귀함수를 사용하게 됩니다.

 

Backtracking 구현시 BFS 와 DFS 의 기본 구조는 유사합니다.

1. 각 노드를 어떻게 방문할 것인가의 관점에서 하위 노드의 정보를 대기열에 넣어주고 모든 곳을 방문합니다.
2. 추가 검색할 노드를 어떻게 관리하느냐에 따라서 순회 방식이 달라지게 되며, 대기열을 Queue 를 통해 관리하는 경우(BFS) 와 Stack (또는 재귀) 를 통해 관리하는 경우(DFS) 로 나뉘게 됩니다.
3. 각 노드를 방문한 다음 visit[ ] 과 같은 방문 처리를 해주어 다시 방문하지 않도록 해야 합니다.
4. 재귀함수를 사용할 경우에는 반드시 빠져나오는 구문을 만들어두어야 합니다.

 

그래프의 인접 행렬 표현을 사용하여 C로 구현된 그래프 순회 알고리즘을 코드로 표현한 예를 추가합니다.

이 코드는 그래프의 깊이 우선 탐색(DFS) 탐색을 수행합니다.

DFS 함수는 주어진 정점 v에서 시작하여 깊이 우선 탐색을 수행하며, 방문한 정점을 인쇄하고 아직 방문하지 않은 이웃 정점을 재귀적으로 탐색한다.

 

이 코드에서 그래프는 그래프라고 불리는 2D 배열을 사용하여 표현되며, 여기서 그래프[i][j]는 정점 i와 j 사이에 간선이 있으면 1이고 그렇지 않으면 0이다. addEdge 함수는 그래프에 간선을 추가하는 데 사용됩니다.

#include <stdio.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];

void initializeGraph() {
    int i, j;
    for (i = 0; i < MAX_VERTICES; i++) {
        visited[i] = 0;
        for (j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
    }
}

void addEdge(int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;
}

void DFS(int v, int numVertices) {
    printf("%d ", v);
    visited[v] = 1;

    int i;
    for (i = 0; i < numVertices; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i, numVertices);
        }
    }
}

int main() {
    int numVertices, numEdges;
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);
    printf("Enter the number of edges: ");
    scanf("%d", &numEdges);

    initializeGraph();

    int i, u, v;
    for (i = 0; i < numEdges; i++) {
        printf("Enter edge %d (u v): ", i + 1);
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }

    int startVertex;
    printf("Enter the starting vertex for DFS: ");
    scanf("%d", &startVertex);

    printf("DFS traversal: ");
    DFS(startVertex, numVertices);
    printf("\n");

    return 0;
}

 

지금까지 그래프 순회, Backtracking 에서 사용되는 깊이 우선 탐색의 개념과 코드를 살펴보았습니다.

 

※ 더 좋은 알고리즘 설명을 위해 내용은 조금씩 업데이트 될 수 있습니다.