BFS / DFS

참조 :

cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html

[Daily PS] 파이썬으로 구현하는 BFS와 DFS

---

map 글 참조

2021.03.25 - [알고리즘/탐색] - map 구현(python)

 

■ BFS (Breadth First Search)

1) 정의 :

너비우선 탐색

탐색점 노드와 같은 depth에 있는 노드부터 queue 이용 먼저 탐색

> queue 이용

> 현재 노드에서 인접한 노드 먼저 탐색

> 복잡도 : O(N) // OS 상의 이유로 BFS가 성능이 조금 더 좋다 // 성능의 이유로 재귀보다는 자료구조 이용한 탐색 추천

graph_list = {1: set([2, 3, 4]),
              2: set([5]),
              3: set([6, 7]),
              4: set([8]),
              5: set([9]),
              6: set([10]),
              7: set([]),
              8: set([]),
              9: set([]),
              10:set([])
}
root_node = 1

from collections import deque

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])
    

    while queue:
        print(f'queue before state : {queue}')
        n = queue.popleft()
        print(f'node now : {n}')
        if n not in visited:
            visited.append(n)
            """deque에 extend 처럼 뒤쪽 인덱스에 같은 depth의 새 노드들 추가"""
            queue += graph[n] - set(visited) # 순서 상관 없이 현재 노드 연결된 자식 노드들
        
        print(f'visited : {visited}')
        print(f'queue after state : {queue}')
    
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))


>>>
queue before state : deque([1])
node now : 1
visited : [1]
queue after state : deque([2, 3, 4])
queue before state : deque([2, 3, 4])
node now : 2
visited : [1, 2]
queue after state : deque([3, 4, 5])
queue before state : deque([3, 4, 5])
node now : 3
visited : [1, 2, 3]
queue after state : deque([4, 5, 6, 7])
queue before state : deque([4, 5, 6, 7])
node now : 4
visited : [1, 2, 3, 4]
queue after state : deque([5, 6, 7, 8])
queue before state : deque([5, 6, 7, 8])
node now : 5
visited : [1, 2, 3, 4, 5]
queue after state : deque([6, 7, 8, 9])
queue before state : deque([6, 7, 8, 9])
node now : 6
visited : [1, 2, 3, 4, 5, 6]
queue after state : deque([7, 8, 9, 10])
queue before state : deque([7, 8, 9, 10])
node now : 7
visited : [1, 2, 3, 4, 5, 6, 7]
queue after state : deque([8, 9, 10])
queue before state : deque([8, 9, 10])
node now : 8
visited : [1, 2, 3, 4, 5, 6, 7, 8]
queue after state : deque([9, 10])
queue before state : deque([9, 10])
node now : 9
visited : [1, 2, 3, 4, 5, 6, 7, 8, 9]
queue after state : deque([10])
queue before state : deque([10])
node now : 10
visited : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
queue after state : deque([])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

> 재귀 구현 방법도 있음

 

---

■ DFS

1) 정의 : 

깊이 우선 탐색

탐색점 노드에 연결되어 있는 노드를 stack에 넣어서 깊이 우선 탐색

> stack 이용

> 현재 노드에서 깊은 곳 부터 탐색

> 복잡도 : O(N) // OS 상의 이유로 BFS가 성능이 조금 더 좋다 // 성능의 이유로 재귀보다는 자료구조 이용한 탐색 추천

graph = {

    1 : set([2,5,9]),
    2 : set([3]),
    3 : set([4]),
    4 : set([]),
    5 : set([6,8]),
    6 : set([7]),
    7 : set([]),
    8 : set([]),
    9 : set([10]),
    10: set([])
}

start = 1

from collections import deque

def DFS_with_adj_list(graph, start):
    
    visited = []
    stack = deque([start])
    
    while stack:
        n = stack.pop()
        
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    
    return visited
    
print(DFS_with_adj_list(graph, start))

>>>
[1, 5, 6, 7, 8, 2, 3, 4, 9, 10]