넓이 우선 탐색 (BFS)

• 거리 기준

거리 (Distance)

• 정점 u부터 정점 v까지의 거리
• 정점 u부터 정점 v까지의 최단경로에 있는 간선의 수 거리

---

• 시작점으로부터 거리를 하나씩 늘리면서 정점을 발견한다.

직전정점 그래프

$G_{\pi}=(V_{\pi},E_{\pi})$

• 시작점으로부터 각 정점을 도달하기 직전에 들려야하는 정점으로 마든 하위 그래프
  • $V_{\pi}=\{v \in V: v.\pi \neq$NIL$\} U\{s\}$
  • $E_{\pi}=\{(v.\pi,v):v\in V_{\pi}-\{s\}\}$
• 직전정점 그래프 $G_{\pi}$는 넓이 우선 탐색 트리이다.
• 모든 정점이 연결되어 있고 $|E_{\pi}|=|V_{\pi}|-1$
• 이때 $E_{\pi}$에 포함된 간선을 트리간선이라고 부른다.

code

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']


def bfs(graph, start_node):
    visited = list()
    need_visit = list()

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited


print(bfs(graph, 'A'))

정점의 색 구분 (Colors of vertices)

• 초기화한 정점 : 흰색 - not discovered
• 발견된 정점 : 회색 - discovered
• 완료된 정점 : 검은색 -finished

수행시간 분석

• 초기화 시간 : $\theta(V)$
• 그래프 탐색 시간 : $O(V+E)$
  • 정점은 최대 한번만 조사된다.
  • 간선은 최대 두 번 조사 된다.