목록BFS (1)

hyeonzzz's Tech Blog

[이코테] 5. DFS/BFS - BFS

BFS BFS : 가까운 노드부터 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 부른다. BFS 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 큐 자료구조에 기초해 구현한다. O(N)의 시간이 소요된다. 일반적인 경우 수행 시간이 DFS보다 좋은 편이다. BFS 코드 from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): # 큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 현재 노드를 방문 처리 visite..
Algorithm 2024. 2. 12. 20:01
이전 Prev 1 Next 다음