[CLRS] [20-3] DFS(Depth-first search)

1. DFS(Depth-first search)?

- 갈 수 있는 가장 깊은 곳까지 내려가는 알고리즘

- Pre/In/Post - order순회

- 재귀를 이용하여 구현 가능하다.

 

- 다음과 같은 그래프를 3을 기준으로 DFS한다고 생각해보자. (인접노드일때 값이 작은것부터 탐색한다.)

- (3 -> 1 -> 0 -> 2 -> 4 -> 5 -> 6) 이 될것이다.

 

2. Code 구현

dfs_visit = list()

def DFS(graph,start_node):
    dfs_visit.append(start_node)
    for each_node in graph[start_node]:
        if (each_node in dfs_visit) == False:
            DFS(graph,each_node)

graph = {0:[1,2],
         1:[0,2,3],
         2:[0,1,4],
         3:[1,4],
         4:[2,3,5],
         5:[4,6],
         6:[5]}

DFS(graph,3)

print(dfs_visit)

====================================================================

Output
[3, 1, 0, 2, 4, 5, 6]