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

DFS

DFS는 ‘깊이 우선 탐색(Depth-First Search Algorithm)’이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색시작 노드를 스택에 삽입하고 방문처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

위 그래프로 깊이 우선 탐색을 한다면 코드는 아래와 같이 작성할 수 있다.

---

Python 코드

def dfs(graph, v, visted): #graph, v, visited가 input, v는 시작점.
  visited[v] = True #현재 노드 방문처리
  print(v, end = '') #방문처리한 노드 출력 
  for i in graph[v]: #graph 속의 노드 중에서(graph[1]의 원소 속에서 i번째 노드가)
    if not visited[i]: #방문 안한 노드가 있다면(방문한 노드 목록에 없다면)
      dfs(graph, i, visited) #다시 방문처리 해주기, 재귀 이용
                              #(i번째 노드로 다시 돌아가기, i가 시작점이 됨)
                              #방문한 노드는 for문에 의해서 다음 노드(graph안에서의 다음 노드)로 넘어가게 됨. 
                              #방문하지 않은 노드만 재귀에 의해서 방문하게 된다.

graph = [
    [],
    [2,3,8], #1은 2,3,8과 연결..
    [1,7],   #2는 1,7과 연결...
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
] 
# 각 노드가 연결된 정보를 리스트로 표현(2차원 리스트)


visited = [False] * 9 #각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
                      #방문 리스트 초기화

#-> visited = [False][False][False][...][...][][][][]

dfs(graph, 1, visited)

---

C언어 코드

#include <stdio.h>

int graph[9][9];
int visit[9];

int dfs(int cur, int n)
{
    int i = 0;
    visit[cur] = 1;
    for (i = 1; i <= n; i++)
    {
        if (graph[cur][i] == 1 && visit[i] == 0)
        {
            printf("%d", i);
            dfs(i, n);
        }
    }
}

int main() {
    
    int start = 1;
    graph[1][2] = 1;
    graph[1][3] = 1;
    graph[1][8] = 1;
    graph[2][1] = 1;
    graph[2][7] = 1;
    graph[3][1] = 1;
    graph[3][4] = 1;
    graph[3][5] = 1;
    graph[4][3] = 1;
    graph[4][5] = 1;
    graph[5][3] = 1;
    graph[5][4] = 1;
    graph[6][7] = 1;
    graph[7][2] = 1;
    graph[7][6] = 1;
    graph[7][8] = 1;
    graph[8][1] = 1;
    graph[8][7] = 1;

    printf("%d", start);
    dfs(start, 8);
    return 0;
}