BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색)

목차

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

• BFS는 그래프나 트리에서 가장 인접한 노드부터 방문하며, 더 이상 인접한 노드가 없을 때 다음 레벨의 노드들을 방문하는 방식으로 탐색하는 알고리즘입니다.
• BFS는 주로 큐를 사용하여 구현합니다.
• BFS의 시간복잡도는 O(V+E)가 됩니다. (V:노드수, E:간선수)
  • 각 노드와 그와 연결된 간선을 한 번씩 확인하므로 위와 같은 시간복잡도를 가지게 됩니다.

• 코드

  • from collections import deque
    
    def bfs(graph,start,visited):
       q=deque([start])
       # 현재 노드를 방문 처리
       visited[start]=True
       # 큐가 빌 때까지 반복
       while q:
          # 큐에서 하나의 원소를 뽑아 출력
          v=q.popleft()
          print(v,end=' ')
          # 해당 원소와 연결된 ,아직 방문하지 않은 원소들을 큐에 삽입
          for i in graph[v]:
             if not visited[i]:
                q.append(i)
                visited[i]=True

  • visited 와 queue를 생각(큐는 deque로 처리)
  • 가중치가 있는 최단거리의 경우 우선순위큐(heapq)로 처리

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

• DFS는 그래프나 트리에서 한 방향으로 깊게 탐색하다가 더 이상 방문할 노드가 없을 때 이전 노드로 돌아와 다른 방향으로 탐색을 계속하는 알고리즘입니다. 
• DFS는 주로 재귀적인 방식으로 구현하며, 스택을 사용하여 구현할 수도 있습니다.
• DFS의 시간복잡도는 O(V+E)가 됩니다. (V:노드수, E:간선수)
  • 각 노드와 그와 연결된 간선을 한 번씩 확인하므로 위와 같은 시간복잡도를 가지게 됩니다.

• 코드
  

  • def dfs(graph,v,visited):
        # 현재 노드를 방문 처리
        visited[v]=True
        print(v,end=' ')
        # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for i in graph[v]:
            if not visited[i]:
                dfs(graph,i,visited)

  • visited 와 재귀 생각
  • 재귀의 경우 런타임 에러가 많이 발생합니다. 따라서 재귀를 사용하였는데 런타임 오류가 발생한다면 아래 코드를 맨 윗줄에 추가해주면 됩니다.

    • import sys
      
      sys.setrecursionlimit(int(1e5))

    • int(1e5)도 안된다면 더 큰 수로 늘려보면 됩니다. 

BFS와 DFS 중 어느 것을 사용해야 할까?

• DFS와 BFS는 각각의 특성에 따라 특정 상황에서 유용하게 사용됩니다. 둘 중 어느 것을 사용할지 결정하는 것은 문제의 특성 및 요구 사항에 따라 다릅니다.
• DFS와 BFS는 결국 완전 탐색입니다. 모든 노드를 다 탐구해들어가는 과정이기 때문입니다. 하지만 그 안에서도 어느 것이 효율적인 경우들이 있습니다.
• DFS와 BFS를 선택할 때 고려할 수 있는 몇 가지 기준점
  • 목표 노드가 멀리 떨어져 있을 것 같은 경우 : BFS는 시작 노드에서 멀리 떨어진 노드를 탐색할 때 깊이가 깊어짐에 따라 많은 수의 노드를 탐색해야 할 수 있습니다. 이런 경우 DFS가 더 효율적일 수 있습니다.
  • 최단 경로가 필요한 경우 : BFS는 시작 노드로부터의 최단 경로를 찾는 데 사용될 수 있습니다. 가장 먼저 목표 노드에 도달하면 그것이 최단 경로가 됩니다.
  • 메모리 사용량 : BFS는 모든 레벨의 노드를 메모리에 저장해야 하므로 공간 복잡도가 높을 수 있습니다. DFS는 현재 경로상의 노드만을 저장하기 때문에 메모리 사용량이 상대적으로 적을 수 있습니다.
  • 사이클 탐지 : 그래프에서 사이클을 탐지하는 경우, DFS를 사용하는 것이 더 적절합니다.
  • 정리
    • BFS : 최단 경로
    • DFS : 목표노드가 멀리 있는 경우, 메모리 사용량, 사이클 탐지