BFS, DFS 정의 _ 순회 탐색 알고리즘

BFS(breadth-first search)

너비우선탐색

S -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

 

 

 

 

BFS는 큐, 딕셔너리, 리스트, 내장함수 개념을 활용

bfs_graph = {   # 그래프를 인접리스트로 표현
    1: [2,3,4],
    2: [1,5,6],
    3: [1,6],
    4: [1],
    5: [6,7],
    6: [5],
    7: [6],
}

def bfs_queue(start_node):
  bfs_list = [start_node]
  queue = [start_node]
  while queue:#외부반복문
    node = queue.pop(0)
    for i in bfs_graph[node]: #내부반복문 
      if i not in bfs_list:
        bfs_list.append(i)
        queue.append(i)

  return bfs_list

bfs_queue(2)
# 1차 : 그래프 연결관계 2차 : edge 연결부분

BFS는 큐 자료구조를 활용( 재귀호출 활용 X)
BFS는 노드가 적은 경우 최단경로를 탐색할 때 유용하다.

 

---

DFS(depth-first search)

깊이우선탐색

 

1 -> 2 -> 4 -> 5 -> 3

 

 

 

 

 DFS는 깊이우선적으로 탐색을 진행하고, 

재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인한다

 

dfs_graph = {   # 그래프를 인접리스트로 표현
    16: [12,13],
    12: [11,14],
    13: [19],
    11: [9],
    9: [91,92],
    91: [],
    92: [],
    14: [],
    13: [19],
    19: [15,20],
    15: [],
    20: [],
}

def dfs_recur(node, dfs_list=[]):
  dfs_list.append(node)   # 리스트에 인접한 노드를 덧붙이는 형태

  for i in dfs_graph[node]:   # 노드의 인접한 노드를 기준으로 반복한다. 
    if not i in dfs_list:
      dfs_list = dfs_recur(i, dfs_list) # 재귀개념
  return dfs_list

dfs_recur(16)  # 시작노드

# 스택을 활용한 DFS 구현하기 

def dfs_stack(start_node):

  dfs_list = []
  stack_list = [start_node]

  while stack_list:
    node = stack_list.pop() # 리스트 메소드

    if node not in dfs_list:
      dfs_list.append(node) # 리스트 메소드

      for i in dfs_graph[node]: 
        stack_list.append(i) # 리스트 메소드

  return dfs_list 

dfs_stack(7)    # 시작노드

 

DFS에서 재귀와 스택의 차이점

재귀 : 간결

스택 : 리스트의 메소트만을 사용하기때문에 이해하기 쉬움, 빠르다

 

출처 : https://developer-mac.tistory.com/64

[코딩테스트 대비] DFS, BFS 정리