BFS, DFS

DFS

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

1. 구현 - stack 활용

list와 dict을 활용하여 인접리스트처럼 표현한 그래프

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']
}

먼저 스택을 활용해서 구현해보면,

def dfs_stack(graph, start_node):
    visit = [] #노드 방문 순서대로 return할 리스트
    stack = [start_node, ] #방문할 노드 스택
    
    while stack:
        #print(stack)
        node = stack.pop() #맨 위 노드 pop하고
        if node not in visit:
            visit.append(node) #해당 노드 방문 및
            stack.extend(graph[node]) #해당 노드의 자식들 스택에 추가
    
    return visit

print(dfs(graph, 'A'))

>> ['A', 'B', 'H', 'M', 'J', 'K', 'L', 'I', 'C', 'D', 'G', 'E', 'F']

👀 stack의 일대기(?)

2. 구현 - 재귀함수

def dfs_recursive(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_recursive(graph, node, visit)
           
dfs_recursive(graph, 'A')

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

BFS

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

구현 - queue 활용

from collections import deque

def bfs(graph, start_node):
    visit = []
    queue = deque()
    queue.append(start_node)

    while queue:
        node = queue.popleft()
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit

print(bfs(graph, 'A'))

>> ['A', 'B', 'C', 'H', 'D', 'I', 'J', 'M', 'E', 'G', 'K', 'F', 'L']

✅ bfs, dfs 둘 다 만약 꼭 방문 순서 찍는 게 아니라면 visit을 리스트 말고 dictionary로 구현해서 방문여부 표시하는 것도 list in 연산에 비해서 시간복잡도 상 효율적일 거 같다!

대충 이런 식으로??

def bfs(graph, start_node):
    nodes = graph.keys()
    visit = {key: value for key, value in zip(nodes, [False for _ in range(len(nodes))])}
    queue = deque()
    queue.append(start_node)

    while queue:
        node = queue.popleft()
        if visit[node] == False: #dictionary 조회로 변경
            visit[node] = True
            queue.extend(graph[node])

    return visit

참고

https://velog.io/@_3juhwan/Python%EC%9C%BC%EB%A1%9C-DFS-BFS-%EA%B5%AC%ED%98%84