너비우선탐색 (Breath-First Search)

lsjoon·2024년 1월 17일

algorithm

Algorithm

목록 보기

14/22

너비우선탐색

루트 노드 ( 임의의 노드 )에서 시작해 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회 방법
‘Prim’, ‘Dijkstra’ 알고리즘과 유사

특징

- 재귀적으로 동작하지 않음
- 어떤 노드를 방문(visited)했었는지 여부를 반드시 검사 (무한루프 방지)
- 방문한 노드를 차례로 저장하고 꺼낼 수 있는 큐 사용(FIFO)
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

장단점

- 장점

너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장
최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음
노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리

- 단점

재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간 필요
노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적

복잡도

[ 노드, 간선 : V, E ]
- 인접 리스트로 표현된 그래프: O(V+E)
- 인접 행렬로 표현된 그래프: O(V^2)

예제

from queue import Queue

GRAPH_SIZE = 1000  # 원하는 크기로 설정

def BFS(x, v):
    visited = [False] * GRAPH_SIZE
    q = Queue()
    q.put(x)  # 처음 방문할 노드를 큐에 담는다.
    visited[x] = True
    while not q.empty():  # 더 이상 다음에 방문할 노드가 없을 때까지
        next_node = q.get()  # 가장 먼저 방문한 노드를 소비하여, 해당 노드의 인접노드를 찾는다.
        print(next_node, end=' ')
        for value in v[next_node]:  # 해당 노드의 인접노드들을 반복하면서
            if visited[value]:  # 이미 방문한 노드라면 생략하고
                continue
            q.put(value)  # 그렇지 않다면 방문한다.
            visited[value] = True

# 예시 그래프
v = [[] for _ in range(GRAPH_SIZE)]
v[1] = [2, 3]
v[2] = [1, 4, 5]
v[3] = [1]
v[4] = [2]
v[5] = [2]

BFS(1, v)

from collections import deque

def bfs(start_node, graph):
    queue = deque([start_node])
    visited = set([start_node])

    while queue:
        curr_node = queue.popleft()

        for next_node in graph[curr_node]:
            if next_node not in visited:
                visited.add(next_node)
                queue.append(next_node)
    return -1

---------------------------------------------------------------
def solution():
    graph = {
        'A': ['B', 'C'],
        'B': ['D', 'E'],
        'C': ['F'],
        'D': [],
        'E': ['F'],
        'F': []
    } 
    
    bfs(A, graph)

최단 경로 알고리즘

현재 위치를 최단 경로로 가기 위해서는 이전 경로와 현재 가중치의 합이다.
그리고 이전 경로는 항상 최단경로이다.

최단 경로 검색방법

가중치가 없을 때 : BFS
가중치가 다르고, 음수 간선이 없을 때
- 1차원 (시작점이 하나) : 다익스트라 (Dijikstra)
- 2차원 (시작점이 여러개) : 플로이드-워셜 (Floyd-Warshall)
가중치가 다르고, 음수 간선이 있을 때 : 벨만-포드 (Bellman-Ford)

너비 우선 탐색(Breadth-First Search, BFS)과의 차이
- BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 알고리즘
- 좀 더 많은 정점을 지나가지만 가중치가 적은 경로가 있을 수 있음
- 가중치 그래프에서는 다익스트라 알고리즘이 가중치의 합이 작은 최단 경로를 찾는데 이용