[알고리즘이론] 파이썬으로 DFS 구현

1. 재귀함수

DFS(깊이 우선 탐색)를 파이썬으로 구현하려면, 일반적으로 재귀 함수를 사용하여 구현할 수 있습니다.

 

아래는 간단한 예제 코드입니다.

# 인접 리스트를 사용한 DFS 구현 예제
def dfs(v, visited, adj_list):
    visited[v] = True  # 현재 노드를 방문 처리
    print(v, end=' ')  # 현재 노드 출력

    for i in adj_list[v]:  # 현재 노드와 인접한 노드 중
        if not visited[i]:  # 방문하지 않은 노드가 있다면
            dfs(i, visited, adj_list)  # 해당 노드를 방문

# 예제 그래프
adj_list = {
    1: [2, 3, 4],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [1, 2, 5],
    5: [2, 4, 8],
    6: [3, 7],
    7: [3, 6],
    8: [5]
}

visited = [False] * 9  # 각 노드 방문 여부를 저장할 리스트
dfs(1, visited, adj_list)  # 1번 노드에서 DFS 탐색 시작

 

위 코드에서 dfs() 함수는 인접 리스트 adj_list와 현재 노드의 인덱스 v, 그리고 각 노드의 방문 여부를 저장할 리스트 visited를 입력으로 받습니다.

 

visited[v] = True와 print(v, end=' ')는 현재 노드를 방문하고 출력하는 부분입니다.

그리고 for문에서는 현재 노드와 인접한 노드들을 하나씩 방문하면서, 이미 방문한 노드는 무시하고 방문하지 않은 노드만 방문하는 재귀적인 함수 호출을 수행합니다.

최초로 dfs() 함수를 호출할 때는 시작 노드의 인덱스와 방문 여부를 저장할 리스트를 입력으로 넣어주면 됩니다.

 

 

2. 스택

DFS 구현 시 스택(Stack)을 사용하는 방법도 있습니다. 스택은 후입선출(LIFO) 구조이므로, DFS에서는 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있으면 해당 노드를 스택에 삽입하고 방문 처리합니다. 그리고 스택에서 꺼낸 노드를 다시 시작점으로 하여 인접한 노드 중 방문하지 않은 노드가 있으면 스택에 삽입하고 방문 처리합니다. 이 과정을 스택이 빌 때까지 반복하면 됩니다.

 

 

아래는 스택을 사용하여 DFS를 구현한 예제 코드입니다.

# 스택을 사용한 DFS 구현 예제
def dfs(start, adj_list):
    visited = [False] * len(adj_list)  # 각 노드의 방문 여부를 저장할 리스트
    stack = [start]  # 시작 노드를 스택에 삽입

    while stack:
        v = stack.pop()  # 스택에서 노드를 꺼내어
        if not visited[v]:  # 방문하지 않은 노드라면
            visited[v] = True  # 해당 노드를 방문 처리하고 출력
            print(v, end=' ')

            # 해당 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 삽입
            for i in adj_list[v]:
                if not visited[i]:
                    stack.append(i)

# 예제 그래프
adj_list = {
    1: [2, 3, 4],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [1, 2, 5],
    5: [2, 4, 8],
    6: [3, 7],
    7: [3, 6],
    8: [5]
}

dfs(1, adj_list)  # 1번 노드에서 DFS 탐색 시작

 

위 코드에서 dfs() 함수는 시작 노드의 인덱스와 인접 리스트 adj_list를 입력으로 받습니다.

visited 리스트는 각 노드의 방문 여부를 저장합니다. 스택은 stack 리스트에 저장되며, 최초로 시작 노드를 스택에 삽입합니다.

그리고 while문에서는 스택이 빌 때까지 노드를 꺼내어 방문하지 않은 노드면 방문 처리하고 출력한 후, 해당 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 삽입합니다.

최초로 dfs() 함수를 호출할 때는 시작 노드의 인덱스와 인접 리스트를 입력으로 넣어주면 됩니다.