DFS

---

• 각 노드에 인접한 노드를 재귀적으로 방문
• 방문한 노드는 다시 방문하지 않음

DFS(u, adj)
{
	u.visited = true;
    
    for each v : adj[u]
   	{	
    	if (v.visited == false)
        	DFS(v, adj);
    }
    
}

DFS(u, adj)
{
	if (u.visited) return;
	u.visited = true;
    
    for each v : adj[u]
   	{	
        DFS(v, adj);
    }
    
}

BFS

---

• 현재 깊이의 모든 정점을 탐색한 후에 다음 깊이 정점 탐색
• 방문한 노드는 다시 방문하지 않음
• 같은 가중치를 가진 알고리즘에서 최단거리 알고리즘으로 사용
  • 다른 가중치 : 다익스트라, 벨만포드 등

BFS(G, u)
{
	u.visited = 1; // 중요
    q.push(u);
    
    while(q.size())
    {
    	u = q.front;
        for each v : adj[u]
        {
			if (v.visited == false)
            {
            	v.visited = u.visited + 1; // 최단거리
            	q.push(v);
            }
        }
    }
    
	
}

• 시작 지점이 여러 개일 경우
  • 처음에 모두 방문 처리 후 모두 큐에 넣기

DFS 와 BFS 비교

---

시간 복잡도 : 동일

DFS

• 메모리를 덜 씀
• 코드가 더 짧음
• 완전탐색에서 자주 사용
• 절단점 등을 구할 수 있음

BFS

• 메모리를 더 씀
• 코드가 더 김
• 가중치가 같은 그래프 내에서 최단거리를 구할 때 자주 사용

💡[TIP]
탐색한다 -> DFS
최단거리 -> BFS