[파이썬 | 알고리즘] 깊이 우선 탐색(Depth-First Search)

지난번에는 너비 우선 탐색(Depth-First Search)에 대해 알아보았습니다.

이번에는 깊이 우선 탐색(Depth-First Search)에 대해 알아보겠습니다.

 

깊이 우선 탐색(Depth-First Search)

DPS(깊이우선탐색)이란 정점들의 자식들(자식노드들)을

먼저 탐색해 나가는 그래프 탐색 알고리즘이다.

DFS

깊이 우선 탐색(Depth-First Search)의 접근법

파이썬에서 제공하는 key와 value를 묶어놓은 dictionary 이용해서

그래프를 표현하고, Queue(visited_queue), Stack(need_visit_queue) 

pop(), extend()메서드를 이용해서 나타낸다.

 

패턴 분석

●dictionary에 저장 할 키값(key)은 키값에 대한 인접노드(values)를 저장한다.

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I'] 

key	values
A	B	C
B	A	D
C	A	G	H	I
D	B	E	F
E	D
F	D
G	C
H	C
I	C
J	I

●visited queue (방문 한 노드를 큐에 저장) - Queue

visited queue

●need_visit queue (방문이 필요한 노드를 스택에 저장) -Stack

need_visit queue

 

이때 삽입 / 삭제는extend()_, pop() 메서드 이용

 

맨 처음 키값(A)을 need_visit queue에 넣는다.

need_visit queue의 마지막 값(A)이 visited queue에 존재하면 마지막 값(A) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(A)의 인접노드(values)추가 (B,C)

visited queue
A

need_visit queue
B	C

need_visit queue의 마지막 값(C)이 visited queue에 존재하면 마지막 값(C) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(C)의 인접노드(values)추가 (A,G,H,I)

visited queue
A	C

need_visit queue
B	A	G	H	I

need_visit queue의 마지막 값(I)이 visited queue에 존재하면 마지막 값(I) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(I)의 인접노드(values)추가 (C,J)

visited queue
A	C	I

need_visit queue
B	A	G	H	C	J

need_visit queue의 마지막 값(J)이 visited queue에 존재하면 마지막 값(J) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(J)의 인접노드(values)추가 (I)

visited queue
A	C	I	J

need_visit queue
B	A	G	H	C	I

need_visit queue의 마지막 값(I)이 visited queue에 존재하면 마지막 값(I) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(I)의 인접노드(values)추가 (C,J)

visited queue
A	C	I	J

need_visit queue
B	A	G	H	C

need_visit queue의 마지막 값(C)이 visited queue에 존재하면 마지막 값(C) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(C)의 인접노드(values)추가 (A,G,H,I)

visited queue
A	C	I	J

need_visit queue
B	A	G	H

need_visit queue의 마지막 값(H)이 visited queue에 존재하면 마지막 값(H) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(H)의 인접노드(values)추가 (C)

visited queue
A	C	I	J	H

need_visit queue
B	A	G	C

need_visit queue의 마지막 값(C)이 visited queue에 존재하면 마지막 값(C) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(C)의 인접노드(values)추가 (A,G,H,I)

visited queue
A	C	I	J	H

need_visit queue
B	A	G

need_visit queue의 마지막 값(G)이 visited queue에 존재하면 마지막 값(G) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(G)의 인접노드(values)추가 (C)

visited queue
A	C	I	J	H	G

need_visit queue
B	A	C

need_visit queue의 마지막 값(C)이 visited queue에 존재하면 마지막 값(C) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(C)의 인접노드(values)추가 (A,G,H,I)

visited queue
A	C	I	J	H	G

need_visit queue
B	A

need_visit queue의 마지막 값(A)이 visited queue에 존재하면 마지막 값(A) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(A)의 인접노드(values)추가 (B,C)

visited queue
A	C	I	J	H	G

need_visit queue
B

need_visit queue의 마지막 값(B)이 visited queue에 존재하면 마지막 값(B) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(B)의 인접노드(values)추가 (A,D)

visited queue
A	C	I	J	H	G	B

need_visit queue
A	D

need_visit queue의 마지막 값(D)이 visited queue에 존재하면 마지막 값(D) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(D)의 인접노드(values)추가 (B,E,F)

visited queue
A	C	I	J	H	G	B	D

need_visit queue
A	B	E	F

need_visit queue의 마지막 값(F)이 visited queue에 존재하면 마지막 값(F) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(F)의 인접노드(values)추가 (D)

visited queue
A	C	I	J	H	G	B	D	F

need_visit queue
A	B	E	D

need_visit queue의 마지막 값(D)이 visited queue에 존재하면 마지막 값(D) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(D)의 인접노드(values)추가 (B,E,F)

visited queue
A	C	I	J	H	G	B	D	F

need_visit queue
A	B	E

need_visit queue의 마지막 값(E)이 visited queue에 존재하면 마지막 값(E) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(E)의 인접노드(values)추가 (D)

visited queue
A	C	I	J	H	G	B	D	F	E

need_visit queue
A	B	D

need_visit queue의 마지막 값(D)이 visited queue에 존재하면 마지막 값(D) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(D)의 인접노드(values)추가 (B,E,F)

visited queue
A	C	I	J	H	G	B	D	F	E

need_visit queue
A	B

need_visit queue의 마지막 값(B)이 visited queue에 존재하면 마지막 값(B) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(B)의 인접노드(values)추가 (A,D)

visited queue
A	C	I	J	H	G	B	D	F	E

need_visit queue
A

need_visit queue의 마지막 값(A)이 visited queue에 존재하면 마지막 값(A) 삭제 / 

존재하지 않으면 visited queue 추가 후 해당 키값(A)의 인접노드(values)추가 (B,C)

visited queue
A	C	I	J	H	G	B	D	F	E

need_visit queue

need_visit queue에 더 이상 값이 없으면 탐색완료

 

깊이 우선 탐색 구현 (파이썬 | Depth-Frist Search)

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

def dfs(graph, start_node):
    visited = list()        #queue 공간
    need_visit = list()     #stack 공간
    
    need_visit.append(start_node)  #맨 처음 노드를 need_visit stack에 추가
    
    while need_visit:             #need_visit stack이 존재 할 때 까지
        node = need_visit.pop()   #맨 뒤 노드를 삭제하면서 새로운 노드에 저장
        if node not in visited:   #맨 뒤 노드가 visited queue에 없다면(중복이 되지 않으면)
            visited.append(node)  #visited queue에 추가
            need_visit.extend(graph[node]) #need_visit stack 뒤에 해당 values값들 연장
    
    return visited

 

코드 테스트(파이썬 Depth-Frist Search)

깊이 우선 탐색 코드 테스트

테스트 결과

 

깊이 우선 탐색 구현 코드가 정상적으로 구현됨

이상으로 [파이썬 | 알고리즘] 깊이 우선 탐색 에 대해 알아보았습니다,