사전 조건
- 각각의 노드로 연결되어 있는 트리구조
- 시작점과 가까운것 위주의 탐색 기법
- 최단 경로 찾기, 미로 찾기에서 사용
-Queue를 사용
동작 방식
- 시작 노드를 탐색하고 방문처리.
- 시작 노드의 연결을 Queue에 담아준다.
- Queue에서 하나씩 꺼낸 값을 시작노드로 설정하고 위 작업을 반복해준다.
- 작업을 반복할 때 이미 탐색한 노드는 탐색하지 않는다.
- 탐색이 완료된 순서대로 출력한다.
동작 순서 예시
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 7, 9]
[1, 2, 3, 4, 5, 7, 9, 6]
[1, 2, 3, 4, 5, 7, 9, 6, 8]
시간 복잡도
O(V + E)
- 인접 리스트 인경우
- 모든 정점에 대해 존재하는 간선만 탐색
- 정점의 수(Vertex) + 간선의 수(Edge)
python 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 29
@ Update : 2020. 01. 29
@ Description : BFS, Breadth-First Search (너비우선탐색)
'''
import queue
def fn_breadthfirst_search(dict_input):
'''
@Description: BFS, Breadth-First Search (너비우선 탐색)
@Arguments Example
# 0~10 사이의 정수라 가정
dict_input = {
1:[2, 3],
2:[1, 4, 5, 7],
3:[1, 5, 9],
4:[2, 6],
5:[2, 3, 7, 8],
6:[4],
7:[5, 2],
8:[5],
9:[3]
}
'''
responce = []
list_end = [1]
queue_list = queue.Queue()
queue_list.put(1)
while queue_list.qsize() >= 1:
int_value = queue_list.get()
for int_resource_index in range(len(dict_input[int_value])):
if dict_input[int_value][int_resource_index] not in list_end:
queue_list.put(dict_input[int_value][int_resource_index])
list_end.append(dict_input[int_value][int_resource_index])
responce.append(int_value)
print(responce)
if __name__ == "__main__":
list_fn_breadthfirst_search_param={
1:[2, 3],
2:[1, 4, 5, 7],
3:[1, 5, 9],
4:[2, 6],
5:[2, 3, 7, 8],
6:[4],
7:[5, 2],
8:[5],
9:[3]
}
print(fn_breadthfirst_search(list_fn_breadthfirst_search_param))