Breadth-First Search(BFS)
input and outputs
Inputs: G =(V,E),시작 정점 s
Outputs:
- d[v]: s에서 v까지 최단 경로 길이(nums of edge)
- π[v]: s->v 최단 경로의 직전 정점(predecessor)
ex) v의 parents 노드(vertex) - d[v]= ∞ : 도달 불가일시 표기법
concepts of Color
White: 아직 발견 안 한 vertex = white 대신 0으로 표기해도 됌
Gray: 발견은 했지만, adjacency vertices를 아직 다 못 본 정점 = 1
Black: adjacency vertices 까지 탐색이 모두 끝난 정점 = 2
pseudo code
BFS(G, s)
1 for each vertex u in V[G] - {s}
2 color[u] ← WHITE
3 d[u] ← ∞
4 π[u] ← NIL
5 color[s] ← GRAY
6 d[s] ← 0
7 π[s] ← NIL
8 Q ← ∅ // 큐 초기화
9 enqueue(Q, s)
10 while Q ≠ ∅
11 u ← dequeue(Q)
12 for each v in Adj[u]
13 if color[v] = WHITE
14 color[v] ← GRAY
15 d[v] ← d[u] + 1
16 π[v] ← u
17 enqueue(Q, v)
18 color[u] ← BLACK
코드 흐름 요약
- 시작 정점 s만 큐에 넣고, 거리 0으로 시작
- 큐에서 하나씩 꺼내면서 (u)
- u의 이웃 v를 보면서 아직 안 간 white(0) 정점이면
- 거리 =d[u]+1
- predecessor = u
- 큐에 넣음
- u의 이웃 다 봤으면 u는 Black(2)
시간복잡도
- 초기화: O(V) +
- 각 정점은 큐에 한번 들어갔다가 나오게 됌: O(V) +
- 각 간선은 최대 한 번씩 adj 리스트에서 검사함: O(E)
따라서 시작 복잡도는 O(V+E)
Que 사용 이유
BFS는 가까운 node 먼저 멀리 있는 node 나중에 방문해야함
-> 거리(depth) 순으로 탐색
개인적 생각 정리
d[v]=무한대 로 두면 메모리를 많이 쓰지않을까?
- 똑같이 4byte씀 ex) float('inf')
BFS로 뭘 할 수 있을까?
-
실제 최단 경로를 구할 수 있음
각 정점 v에 대해 parentv를 저장 후
목적지 t까지 탐색이 끝난 후
t에서 출발해서 parent[t] -> parent[parent[t] -> ~ -> s
이렇게 거꾸로 올라간 경로를 뒤집으면 s->t 최단 경로임 그럼 출력도 가능함 -
그래프의 connected 여부 판별가능
방문한 node 수 < 전체 정점 수 이라면 연결 그래프가 아님 -
각 노드들 탐색 가능
-
특정 노드에서 레벨 white(0), gray(1), black(2)로 s,s와 인접한 정점들, 레벨 1의 이웃들로 나눌 수 있음
-
홀수 cycle 존재 여부 판단(Undirected Graph)
BFS로 Coloring 하면서 두 색으로 Coloring 가능 한지 검사 -> 홀수 길이 cycle 있으면 불가능함
인접한 두 정점이 같은 색이 나올 수 없기 때문
-> 이분 그래프 가능// 이분그래프:그래프 정점을 두 집합 A, B로 나누어서
모든 간선이 A↔B 사이에만 존재하도록 만들 수 있음
예전 백준에서 이 알고리즘으로 문제 풀었던 기억이 난다
