[파이썬 | 알고리즘] 너비 우선 탐색(Breadth-First Search)

지난번에는 순차 탐색(Sequential Search)에 대해 알아보았습니다.

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

 

너비 우선 탐색(Breadth-First Search)

BFS(너비우선탐색)이란 정점들과 같은 레벨에 있는 노드들(형제 노드들)을

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

BFS 

 

너비 우선 탐색(Breadth-First Search)의 접근법

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

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

2개와 pop(0), 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 (방문 한 노드를 큐에 저장)

visited queue

●need_visit queue (방문이 필요한 노드를 큐에 저장)

need_visit queue

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

 

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

need_visit queue의 첫번 째 값(A)이 visited queue에 존재하면 첫번째 값(A) 삭제 /

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

visited queue
A

need_visit queue
B	C

need_visit queue에 있는 첫번 째 값(B)이 visited queue에 존재하면 첫번째 값(B) 삭제 /

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

visited queue
A	B

need_visit queue
C	A	D

need_visit queue에 있는 첫번 째 값(C)이 visited queue에 존재하면 첫번째 값(C) 삭제 /

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

visited queue
A	B	C

need_visit queue
A	D	A	G	H	I

need_visit queue에 있는 첫번 째 값(A)이 visited queue에 존재하면 첫번째 값(A) 삭제 /

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

visited queue
A	B	C

need_visit queue
D	A	G	H	I

need_visit queue에 있는 첫번 째 값(D)이 visited queue에 존재하면 첫번째 값(D) 삭제 /

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

visited queue
A	B	C	D

need_visit queue
A	G	H	I	B	E	F

need_visit queue에 있는 첫번 째 값(A)이 visited queue에 존재하면 첫번째 값(A) 삭제 /

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

visited queue
A	B	C	D

need_visit queue
G	H	I	B	E	F

need_visit queue에 있는 첫번 째 값(G)이 visited queue에 존재하면 첫번째 값(G) 삭제 /

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

visited queue
A	B	C	D	G

need_visit queue
H	I	D	E	F	C

need_visit queue에 있는 첫번 째 값(H)이 visited queue에 존재하면 첫번째 값(H) 삭제 /

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

visited queue
A	B	C	D	G	H

need_visit queue
I	D	E	F	C	C

need_visit queue에 있는 첫번 째 값(I)이 visited queue에 존재하면 첫번째 값(I) 삭제 /

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

visited queue
A	B	C	D	G	H	I

need_visit queue
D	E	F	C	C	C	J

need_visit queue에 있는 첫번 째 값(D)이 visited queue에 존재하면 첫번째 값(D) 삭제 /

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

visited queue
A	B	C	D	G	H	I

need_visit queue
E	F	C	C	C	J

need_visit queue에 있는 첫번 째 값(E)이 visited queue에 존재하면 첫번째 값(E) 삭제 /

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

visited queue
A	B	C	D	G	H	I	E

need_visit queue
F	C	C	C	J	D

need_visit queue에 있는 첫번 째 값(F)이 visited queue에 존재하면 첫번째 값(F) 삭제 /

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

visited queue
A	B	C	D	G	H	I	E	F

need_visit queue
C	C	C	J	D	D

need_visit queue에 있는 첫번 째 값(C)이 visited queue에 존재하면 첫번째 값(C) 삭제 /

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

visited queue
A	B	C	D	G	H	I	E	F

need_visit queue
C	C	J	D	D

need_visit queue에 있는 첫번 째 값(C)이 visited queue에 존재하면 첫번째 값(C) 삭제 /

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

visited queue
A	B	C	D	G	H	I	E	F

need_visit queue
C	J	D	D

need_visit queue에 있는 첫번 째 값(C)이 visited queue에 존재하면 첫번째 값(C) 삭제 /

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

visited queue
A	B	C	D	G	H	I	E	F

need_visit queue
J	D	D

need_visit queue에 있는 첫번 째 값(J)이 visited queue에 존재하면 첫번째 값(J) 삭제 /

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

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

need_visit queue
D	D	I

need_visit queue에 있는 첫번 째 값(D)이 visited queue에 존재하면 첫번째 값(D) 삭제 /

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

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

need_visit queue
D	I

need_visit queue에 있는 첫번 째 값(D)이 visited queue에 존재하면 첫번째 값(D) 삭제 /

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

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

need_visit queue
I

need_visit queue에 있는 첫번 째 값(I)이 visited queue에 존재하면 첫번째 값(I) 삭제 /

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

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

need_visit queue

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

 

너비 우선 탐색 구현 (파이썬 | BreadTh-Frist Search)

graph = dict() #파이썬 딕셔너리를 이용해 key,vlaue값 저장

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 bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node) #맨 처음 노드를 need_visit queue에 추가한다.

    while need_visit: #need_visit queue에 노드가 존재할 때 까지
        node = need_visit.pop(0)  #새로운 노드공간에 need_visit queue의 맨 처음 노드를 저장하면서 need_visit queue에서 뺴냄
        if node not in visited:   #visited queue에 새로운 노드가 값이 없다면 (중복이 되지 않으면)
            visited.append(node)  #visited queue에 need_visit queue의 맨 처음 노드 추가
            need_visit.extend(graph[node]) #need_visit queue 뒤에 해당 vlaues값들 연장

    return visited

 

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

너비 우선 탐색 코드 테스트

테스트 결과

 

너비 우선 탐색 구현 코드가 정상적으로 구현됨

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