DFS: 깊이 우선 탐색

그래프 구조 - 노드(node, vertex)와 간선(edge)로 이루어짐

인접행렬 방식: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

INF = 99999999

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

인접리스트 방식: 연결리스트로 그래프의 연결 관계를 표현하는 방식

graph = [[] for _ in range(3)]

#node k와 edge 크기 n으로 연결된 node d에 대하여: graph[k].append((d, n))
#노드 0에 연결된 노드들에 대한 정보
graph[0].append((1, 7))
graph[0].append((2, 5))

#노드 1에 연결된 노드들의 정보
graph[1].append((0, 7))

#노드 2에 연결된 노드들에 대한 정보
graph[2].append((0, 5))

print(graph)

[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

DFS 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정이 더이상 수행할 수 없을 때까지 반복한다.

* "방문 처리"는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미.

일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러개 있으면 번호가 낮은 순서부터 처리한다.

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [], #0번째 노드와 연결된 노드들의 집합
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5], [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

1 2 7 6 8 3 4 5