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

• 그래프에서 시작 노드에 인접한 노드부터 깊이를 우선하여 탐색하는 알고리즘
• 컴퓨터는 구조적으로 스택의 원리 이용하기에 자료구조 스택없이 구현이 가능(재귀호출)
• 단순 검색 속도 자체는 BFS에 비해 느림

과정

1. 스택의 최상단 노드를 확인

2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 제거

알고리즘 구현

# queue 구현을 위한 deque을 사용
from collections import deque

visited = [False] * 8
graph = [
    [],
    [2,3],      #1
    [1,4,5],    #2
    [1,4,6],    #3
    [2,3,5,7],  #4
    [2,4,7],    #5
    [3,7],      #6
    [4,5,6],    #7
]

def dfs(start):
    global visited;
    if(visited[start]): return;
    visited[start] = True
    print(start, end=' ')
    for idx,node in enumerate(graph[start]):
        dfs(graph[start][idx])
    
dfs(1)