데크 #queue #deque #due #bfs #graph #start #자료구조 #알고리즘 #노드 #node #adj #
-
파이썬 자료구조 알고리즘, BFS -> Queue로 구현Python 2024. 7. 23. 01:46
BFS 저번시간에 배운 DFS는 깊이 우선 탐색으로, 탐색하는 노드를 갈 수 있는 한 최대한 깊이 따라갔다가 더이상 길이 없으면 백해서 다시 노드를 탐색하는 구조였다면 BFS는 Breadth-first search, 너비 우선 탐색이라는 뜻으로, 현재 노드를 시작으로 현재 노드에 인접한 모든 노드들을 먼저 방문한다. 즉, 아래 그래프에서 DFS가 1 > 2 > 5 > 9 > 3 순서로 방문한다면, BFS는 1 > 2 > 3 > 4 > 5 순서로 방문한다. 이번에도 코드로 구현해보자.우선 딕셔너리로 그래프를 작성하고graph = {1: [2, 3, 4],2: [5],3: [6, 7],4: [8],5: [9],6: [10],7: [],8: [],9: [],10: [],} Queue를 사용할거다. 일단 BFS..