DFS & BFS 3
DFS & BFS 3(BFS))
출처 : (이코테 2021 강의 몰아보기) 3. DFS & BFS
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
BFS
BFS는 너비 우선 탐색이라고도 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
코드
#BFS
from collections import deque
def bfs(graph,start,visited):
queue=deque([start])
visited[start]=True
while queue:
v=queue.popleft()
print(v,end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
#각 노드가 연결된 정보를 표현(2차원 리스트)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited=[False]*9
bfs(graph,1,visited)
