최단 경로 알고리즘의 근간...?

너비 우선 탐색 Breadth-First Search

현재 벡터와 연결된 연관벡터들을 방문하고 다음 단계로 넘어가기

연관벡터들을 저장해놔야겠지...? 들어온 순으로 탐색을 이어나가야겠지...?
Queue에다 저장해!

from collections import deque

discovered = [False] * Vector 수

def BFS(graph, start, discovered):
    queue = deque([start])
    discovered[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if(not discovered[i]):
                queue.append(i)
                discovered[i] = True

핵심 로직

모든 벡터는
 1. 아직 발견되지 않음 (discoverd[False])
 2. 발견되었지만 방문하지 않음 (queue.append, discoverd[True])
 3. 방문 처리 됨 (queue.pop)
단계를 거친다!

BFS의 시간 복잡도도 DFS와 마찬가지로 graph를 어떤 자료구조로 표현했냐에 따라 달라진다잉
인접 리스트는 벡터와 에지의 수에 따라 O(V + E)
인접 행렬은 벡터와 다른 모든 벡터를 비교해야하니까 O(V^2)

BFS를 통해 알 수 있는 것

BFS에서 새 벡터를 발견하는데 사용한 에지만을 모은것

• BFS Spanning Tree

BFS Spanning Tree를 통해

• 시작벡터-대상벡터 간의 최단 경로를 구할 수 있다.

최단 경로

BFS를 수행한 결과로 BFS Spanning Tree가 나오게 된다. Spanning Tree와 이름이 비슷하다? 이 뜻은...
BFS는 Spannign Tree 알고리즘의 하나인 Prim 알고리즘의 베이스가 된다는 의미!? (아마도??)

아무튼 BFS를 쓰는 용도는 딱 하나. 최단 경로를 구할 때 씀
시작점에서 각 벡터까지의 거리인 distance를 두고
distance[now] = distance[prev] + 1를 하면 최단 경로를 구하게 되는 거임.

    distance = None
    parent = None # 현재 벡터의 부모 벡터를 알아야 distance[prev]+1을 구할 수 있다.

    def BFS(graph, start):
        nonlocal distance
        nonlocal parent
        # 초기화
        distance = [-1] * len(graph)  # 시작점과의 거리
        parent = [-1] * len(graph)  # 해당 노드의 부모 노드
        #
        queue = deque([start])
        distance[start] = 0
        parent[start] = start # 시작점은 자기 자신을 부모로

        while queue:
            here = queue.popleft()
            for there in graph[here]:
                if(distance[there] == -1):
                    queue.append(there)
                    distance[there] = distance[here] + 1
                    parent[there] = here

    # 시작점에서 v까지의 최단 경로
    def shortest_Path(v, parent):
        path = deque([v])
        while True:
            v = parent[v]
            path.appendleft(v)
            if(parent[v] == v):
                break
        return path

if(distance[there] == -1):
	queue.append(there)
	distance[there] = distance[here] + 1
	parent[there] = here

방문한 적이 있다면 그게 최단 거리이니까.
방문한 적이 없다면 지금이 최단 거리니까.
왜??
distance[N] <= distance[N-1]일 수 없기 때문에
BFS는 이때까지의 에지수가 같은 그룹 순으로 방문되니까.
재방문하는 경우면 이미 이전 그룹에서 방문되었다는거니 최단경로는 이미 정해진거겠지.

그래프의 전체 구조의 정보를 얻기 위한 DFS와 달리
BFS는 벡터간의 거리를 구하기 위해 사용한다.
구조의 정보를 얻기 위해 모든 벡터를 검사하는 탐색에는
BFS는 어울리지 않는다.

더보기

양방향 탐색

MAZERUNNER

‹ 탐색 알고리즘 목록으로