[알고리즘] Network flow : BFS & DFS

(2021.11.12)

알고리즘 수업들으면서 정리하기 19탄

 

w10-3 녹화강의, w11-1 실강

BFS,DFS 내용이다.

 

---

 

 

Network flow

 

graph 알고리즘

- Breadth-first search

- Depth-first search

- Minimum spanning tree (Prim's algorithms)

- Maximum flow (The Ford-Fulkerson method) 

 

 

graph G=(V,E)  로 표현한다.

  - V는 vertices 의 집합 (G.V)

  - E는 edges 의 집합 (G.E)

 

G는 방향성일 수도 있고, 무방향성일 수도 있다. (directed, undirected)

보통 graph는 인접리스트나 인접행렬로 표현한다.

 

 

 

 

 

 

BFS(Breadth-first search): 너비 우선 탐색

 

input: graph G=(V,E)  (directed or undirected) and source vertex s (s∈V)

output: v.d = distance from s to v (v∈V)

 

FIFO queue Q를 이용한다.

 

 

 

 

 

 

performance of DFS

: O(|V|+|E|)

모든 vertex를 한 번은 방문해야 하고, 그 과정에서 모든 edge들을 한 번씩 지나가기 때문이다.

 

 

 

 

DFS(Depth-first search): 깊이 우선 탐색

 

input: graph G = (V,E) (directed, undirected) (+source vertex s 주어지지 않음)

output: 각 vertex마다 2개의 timestamps

  -- u.d: 처음 탐색할 때의 시간

  -- u.f: 탐색이 종료될 때의 시간

(+ u.𝝅: u의 predecessor)

 

colors를 사용한다. --> 알고리즘의 상태를 추적하기 위해서 (u.color)

WHITE: 발견되지 않음

GRAY: 발견되었으나, 탐색 종료하지 않음

BLACK: 탐색 종료됨

(u.d: GRAY, u.f: BLACK)

 

두 개의 timestamps u.d와 u.f 는 1과 2|V| 사이의 값이다.

(방문하는 거 한번, 탐색 종료하는 할 때 한 번해서 총 2번 vertex에 가기 때문이다.)

1≤u.d<u.f≤2|V|

 

 

 

 

 

 

 

 

 

 

performance of DFS

:Θ(|V|+|E|)

모든 vertex는 한 번은 방문하고, 그 과정에서 모든 edge들도 한 번씩 지나가기 때문이다.