[인프런] DFS & BFS

📘 10주완성 C++ 코딩테스트 강의를 수강한 후 정리한 글입니다.

 

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

 

DFS는 그래프를 탐색할 때 쓰는 기법이다.

어떤 노드부터 시작해 인접한 노드들은 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다.

각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘이다.

 

DFS를 구현하는 방법

1️⃣  visited를 확인하고 함수 호출

2️⃣ 함수 호출 후 기저조건으로 함수 return

 

⬇ 수도코드

DFS( u , adj )
	u.visited = true // 해당 노드 방문처리
    for each v in adj[u]
    	if v.visited == false //방문 여부 확인
        	DFS( v, adj )// 방문하지 않은 경우 방문( 재귀 )

 

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

 

BFS는 그래프를 탐색할 때 쓰는 기법이다.

어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘.

같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰인다.

 

 

BFS를 구현하는 방법

Queue를 이용한다.

 

⬇ 수도코드

BFS( G, u )
	u.visited = 1
    q.push(u)
    while( q.size() )
    	u = q.front()
        q.pop()
        for each v in G.adj[u] //같은 깊이의 노드 방문
        	if v.visited == false // 같은 정점 재방문 불가
            	v.visited = u.visited + 1 //최단거리를 도출해낼 수 있음
                q.push(v)

 

---

DFS와 BFS 비교

둘 다 시간복잡도는 인접리스트로 이루어져 있다면, O( V + E ) 이고, 인접 행렬의 경우 O( V**2 )

 

DFS 

1. 메모리를 덜 쓴다.

2. 절단점을 구할 수 있다.

3. 코드가 좀 더 짧으며, 완전탐색의 경우에 많이 쓴다.

 

BFS

1. 메모리를 DFS 보다 더 쓴다.

2. 가중치가 같은 그래프 내에서 최단거리를 구할 수 있다.

3. 코드가 더 길다.