DFS/BFS

그래프

vertex(정점)(node, 노드), edge(간선)으로 구성됨

트리도 그래프의 일종

두 노드가 연결되어 있음 == 두 노드는 인접함

 

구현 방법

인접 행렬 (Adjacency Matrix)

2차원 배열로 그래프의 연결 관계 표현함

연결된 정점은 1로, 아니면 0 (또는 무한 비용 INF) 넣기

- 무조건 2차원 배열을 만들어야 해서 불필요한 공간 필요함

인접 리스트 (Adjacency List)

연결 리스트로 그래프의 연결 관계 표현함

정점의 리스트 배열을 만들어 연결된 정점들을 배열에 넣어서 표현

연결된 정보만을 저장해서 메모리를 효율적으로 사용함

연결된 데이터 하나씩 확인해야 해서 두 노드 연결되어 있는지에 대한 정보 얻는 속도가 느림

vector<int> G[5]; //1~5까지의 정점 가진 그래프
G[1].push_back(3); //정점 1과 연결된 정점 3을 1번 배열에 넣음

 

DFS (Depth-First Search, 깊이 우선 탐색)

그래프에서 깊은 곳을 우선적으로 탐색함

스택 자료구조를 이용함 (선입후출 FILO)

 

동작 과정

- stack 사용

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리를 함 (visited[n] = 1)

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 인접 노드를 스택에 넣고 방문 처리를 함, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

3. 2번 과정을 수행할 수 없을 때까지 반복함

 

- stack 미사용 (재귀 함수)

1. 탐색 시작 노드를 dfs의 인자로 넣고 방문 처리 함

2. 노드의 인접 노드를 찾기 (for문으로)

3. 인접 노드를 인자로 한 재귀 함수 호출 (dfs)

4. 인자로 들어온 노드를 방문 처리 함

5. 2,3을 반복

 

BFS (Breadth First Ssearch, 너비 우선 탐색)

그래프에서 가까운 노드부터 탐색함

큐 자료구조를 이용함 (선입선출, FIFO)

일반적인 경우 DFS보다 실제 수행 시간이 좋음

 

동작 과정

1. 시작 노드를 큐에 삽입 후 방문 처리 함

2. 큐에서 노들르 꺼낸 후 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입, 방문 처리 함

3. 2번을 반복