Python의 DFS 템플릿

DFS란 무엇입니까?

DFS(깊이 우선 검색)는 각 분기에서 가능한 한 멀리 탐색하는 트리/그래프 순회 알고리즘입니다.

위 트리의 DFS 순회는 다음과 같습니다.[0, 1, 3, 4, 2, 5 ,6]

DFS 애플리케이션

DFS의 일부 응용 프로그램은 다음과 같습니다.

무언가를 찾기 위해 명시적 트리를 탐색함

그래프 순회:

그래프의 토폴로지 정렬 찾기

그래프의 사이클 감지

스패닝 트리 찾기

역추적을 사용하여 다음을 수행합니다.

퍼즐 풀기

조합 문제 풀기

템플릿

다음 템플릿을 사용하여 트리/그래프를 간단히 탐색할 수 있습니다.

이진 트리의 DFS

def do_something(root):
        pass

def dfs(root):
    if not root:
        return
    do_something(root)
    dfs(root.left)
    dfs(root.right)

N항 트리의 DFS

def do_something(root):
    pass

def get_children(root):
     pass

def dfs(root):
    if not root:
        return
    do_something(root)
    for child in get_children(root):
        dfs(child)

그래프의 DFS

visited = set()
def do_something(root):
    pass

def get_neighbors(root):
    pass

def dfs(root, visited):
    if root in visited:
        return
    do_something(root)
    visited.add(neighbor)
    for neighbor in get_neighbors(root):            
        dfs(neighbor, visited)

간단한 순회 외에도 자식에서 부모로 값을 전달하거나(반환 값 사용) 부모에서 자식으로 값을 전달할 수 있습니다(함수 매개 변수 사용).

값을 위로 넘기는 예(반환값)

N-ary 트리의 최대 깊이 찾기

def get_children(root):
    pass

def max_depth(root):
    if not root:
        return 0
    depth = 0
    for child in get_children(root):
        depth = max(depth, max_depth(child))
    return depth + 1

값을 아래로 전달하는 예(함수 매개변수)

이진 트리의 인쇄 경로

def dfs_path(root, res):
    if not root:
        return
    res.append(root)
    dfs_path(root.left, res)
    dfs_path(root.right, res)

역추적도 DFS의 변형입니다. 역추적은 전체 트리/그래프를 탐색하지 않습니다. 대신 역추적은 솔루션으로 이어질 수 없는 분기 탐색을 중지합니다.

역추적은 종종 퍼즐이나 조합 문제를 해결하는 데 사용될 수 있습니다.

역추적 템플릿

def condition():
    pass

def do_something(root):
    pass

def get_children(root):
     pass

def backtrack(root):
    if not condition():
        return
    do_something(root)
    for child in get_children(root):
        backtrack(child)