깊이우선탐색(DFS)과 너비우선탐색(BFS)

그래프(Graph)란?

연결되어 있는 객체 간의 관계를 표현하는 자료구조

그래프 G는 (V, E)로 표시

• 정점(vertices)
  • 여러 가지 특성을 가질 수 있는 객체
  • 노드(node)라고도 불림
• 간선(edge)
  • 정점들 간의 관계
  • 링크(link)라고도 불림

DFS란?

• 깊이 우선 탐색(depth-first search)한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행
• 스택(Stack)을 사용하거나 재귀함수 사용

# 재귀함수를 사용한 DFS
depth_first_search(v):
	v를 방문되었다고 표시;
		for all u ∈ (v에 인접한 정점) do 
			if (u가 아직 방문되지 않았으면)
				then depth_first_search(u)

# 스택을 사용한 DFS
dfs_iterative(G, v):
	스택 S를 생성한다. 
	S.push(v)
	while (not is_empty(S)) do 
		v = S.pop()
		if (v가 방문되지 않았으면)
			v를 방문되었다고 표시
			for all u ∈ (v에 인접한 정점) do
				if (u가 아직 방문되지 않았으면)
					S.push(u)

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

BFS란?

• 너비 우선 탐색(breadth-first search)
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐(Queue)를 사용하여 구현됨

# 큐를 사용한 BFS
breadth_first_search(v):
	v를 방문되었다고 표시
	큐 Q에 정점 v를 삽입
	while (Q가 공백이 아니면) do 
		Q에서 정점 w를 삭제
		for all u ∈ (w에 인접한 정점) do 
			if (u가 아직 방문되지 않았으면)
				then u를 큐에 삽입, u를 방문되었다고 표시

• 장점
  • 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
• 단점
  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
  • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
  • 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.