[알고리즘] DFS (깊이우선탐색) 구현해보기 (feat. TypeScript)

 

DFS에 대한 소개

DFS는 Depth-First-Search의 약자로, 깊이우선탐색이라고 합니다.

그래프가 주어졌을 때, 노드(또는 정점, Vertex)를 되도록 깊이 탐색하는 알고리즘입니다.

 

 

DFS 알고리즘을 구현할 때, 스택과 배열을 사용합니다.

재귀함수로 구현하게 되면 재귀함수 자체가 스택 역할을 담당해줍니다.

배열은 노드를 방문했는지를 체크합니다. 노드의 갯수만큼의 크기를 가지고 있습니다.

 

 

DFS 알고리즘 함수에 다음의 정보를 넘겨줌으로써, 그래프 탐색이 시작됩니다.

1. 2차원 배열로 노드와 간선(Edge)을 구현한 그래프

2. 탐색할 노드 번호

3. 방문 여부를 체크할 배열

 

 

 

알고리즘

1.  노드를 스택에삽입한다.

2.  방문하지 않았으면 방문했다고 표시한다.

3.  해당 노드의 인접 노드를 탐색한다. 방문하지 않은 노드이면, 1번과 2번을 실행한다.

4.  현재 노드의 인접 노드를 모두 방문했으면, 스택에서 제거(Pop)한다.

5.  모든 노드를 탐색하게 되면 스택이 빈 상태가 되고, 알고리즘이 종료된다.

 

 

 

시간 복잡도

O(V+E)

노드(V, Vertex)와 간선(E, Edge)의 크기만큼 시간복잡도가 발생합니다.

모든 노드(V)를 방문하고, 인접노드(E 만큼의 크기)를 방문하기 때문입니다.

 

 

 

DFS 알고리즘을 하나씩 실행한 모습

01234567891011121314

 

 

DFS 구현 코드 (with TypeScript)

function dfs(graph: number[][], v: number, visited: boolean[]) {
  visited[v] = true;

  console.log(v, " ");

  for (const i of graph[v]) {
    if (!visited[i]) {
      dfs(graph, i, visited);
    }
  }
}

// 그래프
const graph = [[], [2, 3, 4], [1, 5], [1, 6, 7], [1], [2], [3, 7], [3, 6]];

// 방문체크
const visited = new Array(graph.length).fill(false);

dfs(graph, 1, visited);

 

출력결과

1 -> 2 -> 5 -> 3 -> 6 -> 7 -> 4 순서로 노드를 방문