DFS와 BFS

Intro

dfs와 bfs는 트리의 순회처럼 그래프의 모든 정점을 특정 순서에 따라 방문하는 그래프의 탐색 알고리즘이다.

 

Graph

계층적인 구조보다 좀더 일반적이고 강력한 자료 구조

 

- 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다.

e.g. 여러 도시를 연결하는 도로망, 사람들 간 지인 관계, 웹사이트 간 링크

 

적용할 수 있는 문제

- 철도망의 안정성 분석

- 소셜 네트워크 분석

- 인터넷 전송 속도 계산

- 한 붓 그리기

- 외환 거래

 

암시적 그래프 구조

- 할 일 목록 정리 

- 15-퍼즐

- 게임판 덮기

- 회의실 배정

 

 

 

Tree와의 차이점

Graph는 부모 자식 관계에 대한 제약이 없다.

 

 

그래프 G(V, E)

: 어떤 자료나 개념을 표현하는 vertex들의 집합 V와 이들을 연결하는 edge들의 집합 E로 구성된 자료 구조.

- 정점들과 간선들로 정의된다.

- 정점의 위치 정보나 간선의 순서 등으로 정의되지 않는다.

- 방향(유향) 그래프, 무향 그래프, 가중치 그래프와 같이 속성/제약을 부여할 수 있다.

 

Search Algorithm

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘

 

그래프 순회와 트리 순회의 차이점

그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다.

 

Depth-First Search

: 현재 정점과 인접한 간선들을 하나씩 조사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.

 

- 모든 정점을 발견하는 가장 단순하고 고전적인 방법.

- 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다. (재귀 호출로 구현)

- 주로 스택 또는 재귀로 구현.

 

- 백트래킹 : 한번 방문 후 가능성이 없는 경우 왔던 길을 되돌아간다. (브루트 포스와 달리 즉시 후보를 포기한다.)

- 시간 복잡도

1. 인접 리스트로 구현 : O(|V|+|E|)

2. 인접 행렬로 구현 : O(|V|^2)

 

Breadth-First Search

: 각 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 이 중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장한다. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문한다.

 

- 그래프의 최단 경로를 구하는 문제에서 사용.

- 방문순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다.

- 모든 정점은

1. 아직 발견되지 않은 상태

2. 발견되었지만 아직 방문하지 않은 상태(큐에 저장)

3. 방문된 상태

의 순서를 거친다.

 

- 최단 경로를 찾는 다익스트라 알고리즘, 최소 스패닝 트리 알고리즘 등에서 사용됨.

- 큐로 구현.

- 시간 복잡도(DFS와 같음.)

1. 인접 리스트로 구현 : O(|V|+|E|)

2. 인접 행렬로 구현 : O(|V|^2)

 

 

 

 

출처 - Algorithmic Problem Solving Strategies(구종만), Python Algorithm Interview(박상길)