BFS1 BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색) 목차 BFS(Breadth-First Search, 너비 우선 탐색) BFS는 그래프나 트리에서 가장 인접한 노드부터 방문하며, 더 이상 인접한 노드가 없을 때 다음 레벨의 노드들을 방문하는 방식으로 탐색하는 알고리즘입니다. BFS는 주로 큐를 사용하여 구현합니다. BFS의 시간복잡도는 O(V+E)가 됩니다. (V:노드수, E:간선수) 각 노드와 그와 연결된 간선을 한 번씩 확인하므로 위와 같은 시간복잡도를 가지게 됩니다. 코드 from collections import deque def bfs(graph,start,visited): q=deque([start]) # 현재 노드를 방문 처리 visited[start]=True # 큐가 빌 때까지 반복 while q: # 큐에서 하나의 원소를 뽑아 출력 v.. 2023. 10. 16. 이전 1 다음