DFS와 BFS

DFS(깊이 우선 탐색)

 

-> **스택(혹은 재귀)**

 

 

• 구현 
  • **스택**에 시작 노드를 넣는다
  • 스택이 비어있으면 실행을 멈추고 False 반환
  • 스택의 맨 위 노드가 찾고자 하는 노드라면 탐색을 종료하고 True 반환
  • 3에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를 POP. 스택에 들어온 적이 없는 POP한 노드의 모든 이웃 노드를 찾아 순서대로 스택에 넣는다
  • 3으로 돌아간다

  • DFS(G,u)
    	u.visited = ture
    	for each v ∈ G.Adj[u]
    		if v.visited == false
    			DFS(G, v)
    			
    init()
    	For each u ∈ G
    		u.visited = false
    	For each u ∈ G
    		DFS(G, u)

• 장점
  • 현 경로상의 노드를 기억하기 때문에 적은 메모리 사용
  • 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 찾을 수 있다

• 단점
  • 해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색. 효율성을 높이기 위해 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법 사용
  • DFS를 통해 얻어진 해가 최단 경로라는 보장은 X. DFS는 해에 도착하면 탐색을 종료하기 때문!

 

BFS(너비 우선 탐색)

-> **큐 사용**(재귀적으로 동작 X)

 

• 사용되는 곳
  • 웹 크롤링 : 동적으로 생성되는 무한한 인터넷 페이지를 구글이 크롤링하기 위해서는 BFS 사용
  • 네트워크 브로드캐스트
  • 가비지 컬렉션

 

• 구현

  create a queue Q
  mark v as visited and put b into Q
  while Q is non-empty
  	remove the head u of Q
  	mark and enqueue all (unvisited) neighbors of u

 

• 장점
  • 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장
  • 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다

 

• 단점
  • 경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다
  • 해가 존재하지 않다면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝난다
  • 무한 그래프의 경우 해를 찾지도 못하고 끝내지도 못한다

 

사용

• 최단 거리 문제 -> BFS
• 이동할때마다 가중치가 붙어 이동 or 이동 과정에서 여러 제약이 있을 경우 -> DFS

[BFS]

1. 최소 비용 문제

2. 간선의 가중치가 1인 경우

3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)

https://covenant.tistory.com/132