그래프 DFS

그래프

노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(vertex)라고도 합니다.
간선(Edge): 노드 간의 관계를 선으로 표시한 선입니다.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

DFS (Depth First Search)
갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다.

실행 과정

1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
3. 위 과정을 반복한다.

구현 코드

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited


def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited