목록너비 우선 탐색 (1)

포시코딩

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

BFS란? 한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법. 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 BFS를 적용한다. BFS 구현 방법 1. 큐 BFS는 현재 인접한 노드들을 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. -> 처음에 넣은 노드를 꺼낸다. -> 큐를 쓰면 되겠구나 큐를 사용한다는 점 말고는 DFS에서 스택을 사용하는 방법과 매우 유사하다. 코드로 직접 살펴보자 graph = { 1: [2, 3, 4], 2: [1, 5], 3: [1, 6, 7], 4: [1, 8], 5: [2, 9], 6: [3, 10], 7: [3], 8: [4], 9:..
자료구조알고리즘/이론 2022. 11. 29. 18:02
이전 Prev 1 Next 다음