Python으로 구현한 DFS

DFS 알고리즘은 Stack 자료구조를 사용한다.

그래프 노드를 순회하는데 leaf 노드인 순간까지 앞만 보고 방문한다. 만약 leaf 노드를 만나게 되면, 직전의 분기점으로 돌아가 다시 leaf 노드를 만날 때 까지 방문한다.

소스코드

#!/bin/python

graph = {'A': ['B', 'C', 'D'],
         'B': ['A', 'E', 'F'],
         'C': ['A', 'G'],
         'D': ['A', 'H', 'I'],
         'E': ['B'],
         'F': ['B', 'J'],
         'G': ['C'],
         'H': ['D'],
         'I': ['D', 'K', 'L'],
         'J': ['F'],
         'K': ['I'],
         'L': ['I']}

def DFS(graph, root):
    stack = []
    visited = []
    stack.extend(root)

    while(stack):
        outputFromStack = stack.pop()
        visited.extend(outputFromStack)
        inputToStack = list(set(graph[outputFromStack]) - set(visited))
        inputToStack.sort()
        stack.extend(inputToStack)

    return visited

print(DFS(graph, 'A'))

수행결과

$ ./dfs.py 
['A', 'D', 'I', 'L', 'K', 'H', 'C', 'G', 'B', 'F', 'J', 'E']

소스코드 출처:
https://zetawiki.com/wiki/%ED%8C%8C%EC%9D%B4%EC%8D%AC_DFS