[DFS] Depth-First Search (깊이 우선 탐색)

목적

- Graph의 모든 Node를 Cycle(순환) 없이 탐색하는 방법 중 하나

- 같은 Node를 다시 탐색하지 않음

- 모든 Node를 한 번씩만 탐색

 

과정

1. 가장 위의 Node, Root Node에서 시작

2. 맨 위의 Node를 빼낸 후, 방문 표시(Visited True 표시)

3. 다음, 빼낸 Node와 바로 인접한 Node들을 각각 새로운 Tree, Graph의 Root Node로 간주하여 모든 Node를 탐색할 때까지 2 반복

 

# Using a Python dictionary to act as an adjacency list
graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node):
# graph에서는 하위 node가 상위 node에 연결될 수 있으므로 visited가 필요함 -> tree면 visited가 필요하지 않은 것 같음
    if node not in visited:  
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')

 

 

출처

https://favtutor.com/blogs/depth-first-search-python