[그래프 알고리즘] 깊이 우선 탐색(DFS) 와 너비 우선 탐색(BFS)

깊이 우선 탐색

- 무방향 그래프에서 어떤 정점에 대하여 검색이 끝나면 인접한 정점 중 검색하지 않은 정점을 찾아가 다시 검색하는 방법.

무방향 그래프 G(V,E)를 구성하는 V(G)에 속하는 모든 정점들을 방문하는 방법을 그래프의 운행이라 하고, 스택을 이용하는

깊이 우선 검색(DFS)과 큐를 이용하는 너비 우선 검색(BFS) 방법이 있다.

탐색 과정

- DFS는 정점의 방문 시 최근의 주변 정점을 먼저 방문함.

- 시간 복잡도 O(| V |^2)

 DFS

너비 우선 탐색

- 무방향성 그래프에서 어떤 정점을 검색하고 그 정점에 인접한 모든 정점들을 검색한 후 이정점에 인접한 모든 정점들을 검색

하는 방법으로 큐를 이용.

탐색 과정

- 무방향 그래프G(V,E)에서 시작하며 정점 V를 방문한 후 V에 인접한 아직 방문하지 않은 모든 정점들을 방문. 다시 이 정점에

인접하면서 방문하지 않은 모든 정점들에 대해 너비 우선 탐색 수행함.

- 시간 복잡도 O(|V| + |E|)

BFS

구분	깊이 우선 탐색(DFS)	너비 우선 탐색(BFS)
방문점검	가장 최근에 나타난 주변 정점을 선택	가장 오래 된 주면 정점을 선택
특성	순환 알고리즘, 스택 사용	비순환 알고리즘, 큐 사용
나무 순회 방법	preorder 순회	level order 순회

위상 정렬

- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것.

- 방향 그래프를 대상으로 위상 정렬. 진입 차수가 0 인 정점을 선택, 선택한 정점과 여기에 부착된 모든 간선 제거

- 선택과 삭제 과정을 반복해 모든 정점이 선택/삭제되면 알고리즘 종료.

- 진입 차수 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방.

- 이 과정에서 선택되는 정점의 순서를 위상 순서라함.

- 이 과정 중에 그래프에 남아 있는 정점 중에 진입 차수 0인 정점이 없다면 실패한다.

대그 : 사이클이 없는 방향 그래프. 무사이클 방향 그래프

위상 정렬 : 방향 간선이 한 방향으로만 향하도록 정점을 나열하는 것으로 대그에 대하여 깊이 우선 탐색 알고리즘 적용.

싱크 : 마지막 공정은 그 공정 다음에 오는 공정 없음.

소스 : 첫 공정은 그 공정에 앞서 오는 공정 없음.

표현 방법에는 싱크를 이용한 경우엔 연결리스트 이용.