[파이썬] 자료구조 깊이우선탐색(DFS)

'''
재귀함수 처리 못하면 스택에 매개변수, 지역변수, 복귀주소 저장
'''
def DFS(x):
    if x>0:
        DFS(x-1)
        print(x)

if __name__=="__main__":
    DFS(3)

재귀함수를 dfs 방식으로 구현한 예시이다

 

'''
print root역할 , 위치에따라 순회 종류 결정됨
DFS(v*2)
print(v,end=' ') #중위순회
DFS(v*2+1)

DFS(v*2)
DFS(v*2+1)
print(v,end=' ') #후위순회 ex) 병합정렬
'''

def DFS(v):
    if v>7:
        return
    else:
        print(v,end=' ') #전위순회
        DFS(v*2)
        DFS(v*2+1)
        
if __name__=="__main__":
    DFS(1)

print에 위치에따라 순회 종류가 결정된다.

print의 역할이 root 역할인데 print를 먼저 찍으면 전위순회, 가운데에 찍으면 중위순회, 마지막에 찍우면 후위순회 방식인것이다.