DFS

<목차>
1. 개념
2. 예시
3. 구현

1. 개념

• Depth First Search (깊이 우선 탐색)
• 위에서 아래로 찾는 방식
• 이미 들린 노드는 재방문 안하고, 방문하지 않은 노드만 계속 탐색한다
• 활용 범위 —> 스택, 큐, 재귀함수

2. 예시

3. 구현

• graph 는 ABCDEFGHIJ 순서로 작성했으며 각 알파벳을 돌 때 이웃하는 요소들을 매칭시켜줬다.

graph = dict()

graph['Onion'] = ['Rice_ball', 'Poo']
graph['Rice_ball'] = ['Onion', 'Egg']
graph['Poo'] = ['Onion', 'Celery', 'Tofu', 'Pumpkin']
graph['Egg'] = ['Rice_ball', 'Kimchi', 'Peach']
graph['Kimchi'] = ['Egg']
graph['Peach'] = ['Egg']
graph['Celery'] = ['Poo']
graph['Tofu'] = ['Poo']
graph['Pumpkin'] = ['Poo', 'Tomato']
graph['Tomato'] = ['Pumpkin']

def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐
    visited.append(start)

    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited

result = dfs_recursive(graph, 'Onion')
print(" -> ".join(result))

참고

https://data-marketing-bk.tistory.com/entry/DFS-완벽-구현하기-파이썬