DFS(Depth First Search; 깊이 우선 탐색) 파이썬 / 자바스크립트 구현

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념

■ 루트 노드[또는 임의의 노드]에서 시작하여 형제 (sibling) 노드로 넘어가기 전에 시작한 분기의 마지막 노드까지 깊게 탐색하는 방법

■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법

■ 스택 또는 재귀함수를 이용하여 구현

 

2. DFS 노드 방문 순서

■ 결과 : 1 → 2 → 4 → 5 → 6 → 3 → 7 → 10 → 8 → 9

    - step1) 도달 가능한 마지막 노드(막다른 길)까지 이동한다.

    - step2) 지나처 온 최근 갈림길(형제노드)로 되돌아 간다.

    - step3) 모든 노드를 탐색할 때까지 step1과 step2를 반복한다.

 

3. 그래프 표현

■ 그래프는 인접 리스트로 보기 쉽게 표현할 수 있다.

1	2, 3
2	1, 4
3	1, 7, 8, 9
4	2, 5, 6
5	4
6	4
7	3, 10
8	3
9	3
10

 

■ 인접리스트는 2차원 배열[리스트] 또는 테이블[dictionary] 자료구조로 정의할 수 있다.

 

4. 파이썬 코딩

def dfs(graph, start, visited = []):
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
 
    return visited
 
 
if __name__ == '__main__':
    graph = dict() 
    graph['1'] = ['2', '3']
    graph['2'] = ['1', '4']
    graph['3'] = ['1', '7', '8', '9']
    graph['4'] = ['2', '5', '6']
    graph['5'] = ['4']
    graph['6'] = ['4']
    graph['7'] = ['3', '10']
    graph['8'] = ['3']
    graph['9'] = ['3']
    graph['10'] = ['7']
 
    result = dfs(graph, '1')
    print(result)

 

5. JavaScript 코딩

function dfs(graph, v, visited = []) {
    
    visited[v] = true;
    console.log(v);
  
    for (let node of graph[v]) {
      if (!visited[node]) {
        dfs(graph, node, visited);
      }
    }
  }
 
 
graph = []
graph['1'] = ['2', '3']
graph['2'] = ['1', '4']
graph['3'] = ['1', '7', '8', '9']
graph['4'] = ['2', '5', '6']
graph['5'] = ['4']
graph['6'] = ['4']
graph['7'] = ['3', '10']
graph['8'] = ['3']
graph['9'] = ['3']
graph['10'] = ['7']
 
result = dfs(graph, '1')
console.log(result)