깊이 우선 탐색 편집하기 (부분)

== 기본 DFS ==
단순히 모든 노드를 방문하기 위한 목적으로, 가장 간단하게 구현한 DFS를 의미한다.

=== 기본 DFS의 동작 방식 ===

# 시작 노드를 방문하고 스택에 넣는다. 
# 스택의 최상단 노드에서 방문하지 않은 인접 노드를 찾는다. 
# 방문하지 않은 노드가 있으면 해당 노드를 방문하고 스택에 넣는다. 
# 방문하지 않은 노드가 없으면 스택에서 노드를 제거하며 백트래킹(Backtracking)한다. 
# 스택이 비어 있으면 탐색이 종료된다.

=== 기본 DFS의 구현 ===
DFS는 스택을 명시적으로 사용하는 '''반복문 방식'''과, 함수 호출 스택을 활용하는 '''재귀 방식'''으로 구현할 수 있다.

==== 반복문을 이용한 DFS ====
<syntaxhighlight lang="python">
def dfs_iterative(graph, start):
    stack = [start]
    visited = set()

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")

            for neighbor in reversed(graph[node]):  # 스택이므로 뒤에서부터 방문
                if neighbor not in visited:
                    stack.append(neighbor)

# 그래프 표현 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_iterative(graph, 'A')
# 출력: A C F B E D
</syntaxhighlight>

==== 재귀를 이용한 DFS ====
<syntaxhighlight lang="python">
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()

    if node not in visited:
        visited.add(node)
        print(node, end=" ")

        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

# 그래프 표현 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_recursive(graph, 'A')
# 출력: A B D E F C
</syntaxhighlight>