[Algorithm] DFS & BFS

DFS( Depth-First Search)

• 깊이우선탐색(DFS) : 스택 자료구조(혹은 재귀함수)를 이용, 깊은 부분을 우선적으로 탐색하는 알고리즘
  1. 탐색 시작 노드를 스택에 갑입하고 방문 처리를 합니다.
  2. 스택의 최상단 노드에 방문하지 않는 입접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
• DFS, BFS 둘 다 시간 복잡도는 같다
• 실제로는 스택영역(혹은 재귀함수)를 사용하지 않는 BFS(반복문)로 푸는 것이 더 빠를 수 있다

graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9

def dfs(graph, v, visited) :
  visited[v] = True
  print(v, end=" ")

  for i in graph[v] :
    if not visited[i] :
      dfs(graph, i, visited)

 

BFS (Breadth-First Search)

• BFS는 너비우선탐색
• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조 사용
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
  2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 합니다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

from collections import deque

graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9

def bfs(graph, start, visited) :
  queue = deque([start])
  visited[start] = True

  while queue :
    #값에 접근한다.
    v = queue.popleft()
    print(v, end=" ")

    #인접 노드들 중 방문가능한 노드의 경우 방문처리 후 큐에 넣는다.
    for i in graph[v] :
      if not visited[i] :
        visited[i] = True
        queue.append(i)