파이썬 DFS

1 개념

Python Depth First Search, 깊이 우선 탐색

• 파이썬으로 DFS 구현
• 스택을 사용하여 구현

출력	기존 입력	새로운 입력 (자손)
		A
A		BCD
D	BC	HI
I	BCH	KL
L	BCHK
K	BCH
H	BC
C	B	G
G	B
B		EF
F	E	J
J	E
E

2 구현

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)
        #print(outputFromStack)
        inputToStack = list(set(graph[outputFromStack]) - set(visited))
        inputToStack.sort()
        stack.extend(inputToStack)

    return visited

print(DFS(graph, 'A'))

['A', 'D', 'I', 'L', 'K', 'H', 'C', 'G', 'B', 'F', 'J', 'E']

3 같이 보기

• 깊이 우선 탐색