BFS   Breadth First Serach   너비 우선 탐색

1. 너비 우선 탐색 방법 (Breadth First Serach, BFS)

  ㅇ 우선 가까운 인접 노드를 모두 방문한 후에, 그 다음 가까운 인접 노드를 방문하며 진행하는 방법
     - 목표 정점을 탐색할 때, 시작점에 가까운 근처 정점부터 탐색하는 방법 

  ㅇ 특징
     - 사용 자료구조  
        . 선입선출(FIFO)인 `큐` 자료구조를 활용하여, 반복 구조로 구현
     - 가까운 노드 우선이므로, 여러 경로 존재할 경우,
        . 자연스럽게 최단 경로를 일러줌
     - 중간에 거치는 정점들을, 방문 리스트로써, 저장해 둘 필요 있음
        . 기 방문 노드는 다시 방문 않토록, 방문한 노드를 체크할 필요 있음

  ㅇ 구현 방법  :  큐를 이용한 반복 구조로 구현
     - DFS(깊이우선탐색)와 달리 재귀함수로 구현 불가하여,
     - 선입선출(FIFO)인 `큐` 자료구조를 활용하여, 반복 구조로 구현

  ㅇ 시간복잡도 :  O(V+E)
     - (V : 노드 수, E : 간선 수)

  ㅇ 알고리즘의 표현
     - 입력 : 특정 그래프(G), 시작 정점(v)
     - 출력 : 모든 도달 가능 (방문 표시한) 정점들에 대한 배열
        . (방문 여부 true/false) 또는 (각각의 경로 길이)
     
  ㅇ 용도 
     - 다익스트라 알고리즘 등에 쓰임


2. 알고리즘 구현 例)

  ㅇ 구현 특징
     - 자료구조  : 선입선출(FIFO)인 `큐` 자료구조를 활용
     - 입력 : 특정 그래프(G), 시작 정점(v)
        . 여기서, G는 인접 리스트에 의한 그래프 표현으로 가정 함
     - 외부 데이터 : 방문한 정점들이 열거된, 크기가 |G|인, 배열 또는 리스트 (visited)
        . visited[i]가, true이면 이미 방문, false 이면, 미 방문
     - 출력 : 큐에서 노드를 가져올 때 마다 해당 노드 번호 출력 
        . 탐색되며 거치는 경로 순서대로 노드 번호가 출력됨

  ㅇ 슈도 코드
     
BFS(G, start)
    큐 Q에 정점 start(시작 노드)를 삽입
    start(시작 노드)를 방문했다고 표시
    while 큐가 빌 때까지 수행
        큐 Q에서 정점 하나를 가져오기 (제거)
        가져온 노드 출력
        for 가져온 정점 주위 모든 인접 정점들에 대해 반복 수행
            if 인접 정점이 미방문이면
                큐 Q에 해당 인접 정점을 삽입
                해당 인접 정점을 방문했다고 표시


  ㅇ 파이썬 코드
     
def bfs(graph, start) :
    queue = [start]
    visited = [start]
    while queue :
        v = queue.pop(0)
        print(v, end=' ')
        for w in graph[v] :
            if w not in visited :
                queue.append(w)
                visited.append(w)

     - [참고] 사용 데이터 유형
        . 그래프 표현 : 파이썬 딕셔너리(graph)
           .. 형식 : graph = { 1 : [2,3,8], 2 : [1,7], ... }
        . 시작 노드 : 숫자(start)
        . 방문 여부 기록 : 파이썬 리스트(visited)
        . 탐색 관리용 큐 : 파이썬 리스트(queue)
           .. 삽입 : queue.append(), 추출 : queue.pop(0)