https://www.youtube.com/watch?v=CJiF-muKz30&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=20

19강 BFS 알고리즘

그래프 내에서

이러한 bfs는

이용한다는 점이 특징이구요

출발지점 즉 시작 노드를 큐에 넣고

2번에 과정을

자 큐에서 노드를 꺼낸뒤에 그 꺼낸 노드의 인접 노드중에서 방문하지 않는 노드를 모두

큐에 넣고 방문처리를 수행합니다

방문을 수행한다는 특징이 있었는데요

이 bfs는 한번에 전부 큐에 넣는다는점이 특징입니다

조건에서의 최단경로 문제를 해결하기 위한 목적으로도 효과적으로 사용될수 있습니다

또한 큐 자료구조가

숙지하실 필요가

동작예시를 이렇게 dfs때와 동일하게

노드 부터 출발한다고 해볼게요 자 그러면 가장 먼저 시작노드인 1번 노드를 큐에 넣고

의 원소가 위에서 들어와서 아래로 나간다고 가정할게요 자 그래서 이제

그 꺼낸 노드의 인접노드중에서

자 그래서 큐에 들어있던 원소 1을 꺼내서 이제 1에 대해서 처리를 하는거에요

칠했구요 이와같이 회색으로 칠했습니다

큐에서 노드 1을 꺼내 방문하지 않은 인접노드인 238을

큐에놓고 방문처리하는것을 확인할 수있습니다

작은번호부터 넣는다고

이어서 큐에서 노드 2를 꺼내서 현재인접한 노드인 1과 7을 확인하는데요 1은 이미

방문처리가 되어있기 때문에 이7만 큐에넣고 방문처리합니다

큐에서 꺼내서 인접한 노드를 확인해서

큐에 넣고 방문처리 합니다

그래서 8번노드를 꺼내지만

자그래서 이렇게 넓게 2 3 8 부터 차례대로 방문하는 것을 확인할수 있어요

1번 노드부터 이 가까운 노드부터

이시작노드인 1번으로부터 거리가 2인걸 확인할 수 있죠

그렇기 때문에 거리가 2인노드 7 4 5 가 차례대로 방문된걸 확인 할 수 있구요

거리가 가장먼 6번 노드가 가장 마지막으로 탐색되는걸 확인할 수 있습니다

이므로 꼭 기억해 주세요


from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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]
]

#각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9



# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

자 이렇게 큐를 위해서 하나의 뎃 라이브러리를 불러와 주시고요