[Algorithm] 4-(3). DFS(Depth-First Search)

[Algorithm] 4-(3). DFS(Depth-First Search)

 

 

깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

 

1. 그래프의 기본구조

 

노드와 간선으로 표현된다. 노드를 정점이라고도 말한다.

 

그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있으면 인접하다고 표현한다.

 

 

+ 인접 행렬과 인접 리스트에 대한 개념을 확실히 해야 한다.

 

인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

 

파이썬에서 리스트로 행렬을 표시할 때에는

graph = [
	[0, 7, 5],
	[7, 0, inf],
	[5, inf, 0]
]

이런 식으로 표현을 한다. 자기 자신에게는 간선을 연결할 수 없으므로 0으로 표시한다. 연결이 되어 있지 않은 노드끼리는 무한(inf)의 비용이라고 작성한다.

 

DFS는 스택 자료구조(혹은 재귀 함수)를 이용한다.

 

 

2. 동작 과정

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (매번 최상단 노드를 기준으로 해서)
3. 더 이상 (2) 번의 과정을 수행할 수 없을 때까지 반복한다.