너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

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

• 최단 거리, 최소 비용과 같이 최솟값과 관련된 문제 해결에 사용.
• 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다.
• 모든 경로에 대한 동시 탐색 가능.
• 최대 경로를 몰라도 사용 가능 → 최단 거리, 최소 비용 등을 구하기 좋다.
• 큐(Queue) 사용. → FIFO 구조

절차

1. 저장된 정점 중 첫 번째 정점을 선택하여 저장된 정점에서 제거
2. 제거한 정점에서 해야 할 작업 진행
3. 제거한 정점과 연결된 정점 중 방문하지 않은 모든 정점 저장(2, 3번은 순서가 바뀌어도 됨)
4. 저장된 정점에 모든 노드가 제거될 때까지 1~3번 과정 반복

1번 정점 탐색 시작

 

 

시작 정점을 저장한 뒤 방문 표시(회색 처리).

 

첫 번째 단계로 저장된 첫 번째 정점인 1을 제거함

 

 

1번과 연결되고 아직 방문하지 않은 모든 정점(2, 3, 4)을 저장.

방문하지 않은 정점을 저장할 때 반드시 방문했다는 표시를 남겨줌.

 

 

첫 번째 과정으로 돌아가서 저장된 정점 중 가장 첫 번째 정점인 2번 정점 제거.

 

2번 정점과 연결되고, 아직 방문하지 않은 모든 정점(5)을 저장.

2번 정점의 모든 작업이 완료되었으므로 첫 번째 과정으로 돌아감.

 

저장된 정점 중 가장 첫 번째 정점이 3이므로 3번 정점을 제거

 

3번과 연결되고 아직 방문하지 않은 정점(6)을 저장.

3번 정점의 작업이 완료되었으므로 4, 5번 정점 작업을 해야 하지만 두 정점과 연결된 모든 정점이 모두 방문한 상태이므로 넘어간다.

 

 

6번 정점과 연결되고, 아직 방문하지 않은 정점(7)을 저장.

첫 번째 과정으로 돌아가 7번 정점을 선택하고 저장된 정점에서 삭제.

 

 

7번 정점까지 방문했다면 그래프의 모든 정점을 방문했으므로 BFS 종료.

 

구현

graph = [[], [2, 3, 4], [5], [6], [6], [6], [7], []]

def bfs(start):
    chk = [False] * 1010
    q = []
    
    q.append(start)
    chk[start] = True
    
    while len(q):
        cur = q[0]
        q = q[1:] # q.pop()
        print(cur)
        for i in graph[cur]:
            if chk[i] is False:
                chk[i] = True
                q.append(i)

bfs(1)

graph을 이중 리스트(중첩 리스트)로 표현.

예를 들어 graph[1]에는 1번 노드와 연결된 노드(2, 3, 4번 노드)들을 저장한다.