BFS와 DFS

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

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택

ex) A,B사이에 존재하는 경로를 찾는 경우, A에서 가까운 곳 부터 탐색

그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
-> 이를 검사하지 않을 경우, 무한루프에 빠질 위험이 있다.

 

BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다.

->프림과 다익스트라 알고리즘과 유사하다.

 

BFS(G,k)
q.push(G.root)
root.visit = true

while !q.isEmpty()
node r = q.front()
q.pop()
for each n is adjacent to r
	if n.visit == false
		n.visit = true
        q.push(n)

 

 

---

 

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

 

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

미로를 탐색할 때 한 방향으로 갈 수 있을때까지 계속 가다가 더 이상 갈 수 없게 되명

다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사

 

사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

트리 순회는 모두 DFS의 한 종류이다.
어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다,

 

DFS(Start,Goal)
stack S
S.push(Start)
Start.visit = true
while S is not empty
Node n = S.first()
S.pop()
if n == Goal
	return Node
else
	if(n.visit == false)
    	n.visit = true
        S.push(n.child)