너비 우선 탐색(Breadth-First Search)
1. 개념
정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식
-> 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있다.
코드
그래프 생성
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 bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
Author And Source
이 문제에 관하여(너비 우선 탐색(Breadth-First Search)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wnsgur9701/너비-우선-탐색Breadth-First-Search저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)