[Python] BFS

• 그래프 탐색
  • 깊이 우선 탐색 (Depth First Search, DFS)
  • 너비 우선 탐색 (Breadth First Search, BFS)
• 너비 우선 탐색
  • 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 (인접정점들 순으로... -> 선입선출 형태의 자료구조인 큐 활용)

BFS 예제 그래프

# 처리 = visited

def BFS(G,v):                   # 그래프 G, 탐색 시작점 v
    visited = [0]*(n+1)         # n : 정점의 개수
    queue = []                  # 큐 생성
    queue.append(v)             # 시작점 v를 큐에 삽입
    while queue:                # 큐가 비어있지 않는 경우
        t = queue.pop(0)        # 큐의 첫번째 원소 반환
        if not visited[t]:      # 방문되지 않는 곳이라면
            visited[t] = True   # 방문한 것으로 표시
            visit(t)            # 정점 t에서 할일
        for i in G[t]:          # t와 연결된 모든 정점에 대해
            if not visited[i]:  # 방문되지 않은 곳이라면
                queue.append(i) # 큐에 넣기

❗ 위 방법을 쓸 경우 중복이 있을 때 큐가 무수히 많이 늘어날 수 있음

 

# 큐에 넣었다. = visited 

def BFS(G,v,n):                             # 그래프 G, 탐색 시작점 v
    visited = [0]*(n+1)                     # n : 정점의 개수
    queue = []                              # 큐 생성
    queue.append(v)                         # 시작점 v를 큐에 삽입
    visited[v] = 1
    while queue:                            # 큐가 비어있지 않는 경우
        t = queue.pop(0)                    # 큐의 첫번째 원소 반환
        visit(t)                            # 정점 t에서 할일
        for i in G[t]:                      # t와 연결된 모든 정점에 대해
            if not visited[i]:              # 방문되지 않은 곳이라면
                queue.append(i)             # 큐에 넣기
                visited[i] = visited[t] + 1 # t으로부터 1만큼 이동 (v로부터 얼마나 떨어져 있는지 표시)

 

❗❗❗ DFS,BFS 둘 중 어떤 것을 사용해야하는지 공부!!!!!!

DFS 같던 길을 또 갈 수 있음(중복방문)