🎨 단순한 구현

반복문으로 구현해서 DFS/BFS를 이해하기 쉽다!

다음은 dict와 list를 이용한 탐색할 graph 이다.

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

DFS

list를 stack의 용도로 쓰고 있다.

  1 def dfs(graph, start_node):
  2     visit = list()
  3     stack = list()
  4
  5     stack.append(start_node)
  6
  7     while stack:
  8         node = stack.pop()
  9         if node not in visit:
 10             visit.append(node)
 11             stack.extend(graph[node])
 12
 13     return visit

BFS

list를 queue의 용도로 쓰고 있다.

  1 def bfs(graph, start_node):
  2     visit = list()
  3     queue = list()
  4
  5     queue.append(start_node)
  6
  7     while queue:
  8         node = queue.pop(0)
  9         if node not in visit:
 10             visit.append(node)
 11             queue.extend(graph[node])
 12
 13     return visit

한계점

위 코드는 효율성이 많이 떨어진다.

1. bfs에서 queue는 python의 queue를 사용하는 게 효율적이다.

python의 list는 stack처럼 사용된다.
bfs 코드에서는 stack을 queue로 사용해서 pop(0)을 하는데,
pop(0)의 시간 복잡도는 O(n)이기 때문에 비효율적이다.

2. visit은 list 대신 set나 dict를 사용하는 효율적이다.

python에서 dict는 Hash table 역할을 한다. 원소의 중복 여부를 key로 탐색하기에 평균 O(1)의 시간 복잡도를 갖는다.

🎨 보완

programiz 사이트에서 괜찮은 코드를 찾을 수 있었다.

BFS

list 대신 collections 모듈의 deque를 이용한다.
visited도 set로 구현한다.

import collections

# BFS algorithm
def bfs(graph, root):

   visited, queue = set(), collections.deque([root])
   visited.add(root)

   while queue:

       # Dequeue a vertex from queue
       vertex = queue.popleft()
       print(str(vertex) + " ", end="")

       # If not visited, mark it as visited, and
       # enqueue it
       for neighbour in graph[vertex]:
           if neighbour not in visited:
               visited.add(neighbour)
               queue.append(neighbour)


if __name__ == '__main__':
   graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
   print("Following is Breadth First Traversal: ")
   bfs(graph, 0)

시간 복잡도는 O(V + E)로 V는 node 개수이고, E는 edge 개수이다.

DFS

재귀로 구현한 코드이다.
visited도 set로 구현한다.

# DFS algorithm
def dfs(graph, start, visited=None):
   if visited is None:
       visited = set()
   visited.add(start)

   print(start)

   for next in graph[start] - visited:
       dfs(graph, next, visited)
   return visited


graph = {'0': set(['1', '2']),
        '1': set(['0', '3', '4']),
        '2': set(['0']),
        '3': set(['1']),
        '4': set(['2', '3'])}

dfs(graph, '0')

시간 복잡도는 O(V + E)로 V는 node 개수이고, E는 edge 개수이다.

✨ 내가 작성한 코드

재귀를 이용해서 DFS를 작성해봤다.
위의 graph를 사용했다.

def dfs(graph, start_node, visit=list()):
   visit.append(start_node)
   print(start_node, end=' ')
   
   for node in graph[start_node]:
       if node not in visit:
           dfs(graph, node, visit)

dfs(graph, 'A')

>> A B C D E F G H I J K L M

🎁 Reference

• 코딩장이 블로그 - [python] 파이썬으로 bfs, dfs 구현해보기
  https://itholic.github.io/python-bfs-dfs/
  

• collections 모듈 사용법
  https://docs.python.org/3/library/collections.html#collections.deque

• programiz 자료
  https://www.programiz.com/dsa/graph-dfs
  https://www.programiz.com/dsa/graph-bfs