DFS

- 깊이 우선 탐색 

- 스택 자료구조, 재귀 함수 이용

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리함

2. 스택의 최상단 노드에  방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함.

   없다면 스택에서 최상단 노드를 꺼냄

3. 2번 과정을 수행할 수 없을 때 까지 반복

 

 

def dfs(graph, v, visited):
    visited[v] = True
 
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

우선 노드를 방문 처리 해주고, 그 노드안의 원소들 중 방문 처리 되지 않은 노드가 있으면 방문 처리를 해준다.