BFS

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

• BFS는 그래프의 모든 정점을 탐색하는 알고리즘

• 가장 가까운 정점부터 우선적으로 탐색하는 방식

• 특징

  • 재귀적으로 동작하지 않는다
  • 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 (무한 루프의 위험)
  • 방문한 노드들을 차례대로 저장 한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다
    • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다

• Prim 알고리즘, 다익스트라 알고리즘(Dijkstra’s Algorithm)

과정 설명

1. 시작 정점 선택: 탐색을 시작할 정점을 선택합니다.
2. 인접 정점 큐에 추가: 현재 정점에 인접한 모든 정점을 큐에 추가합니다.
3. 큐에서 정점 추출: 큐에서 정점을 하나씩 추출하며 탐색합니다.
4. 방문 체크: 방문한 정점은 체크하여 중복 방문을 방지합니다.

Sudo Code

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True