DFS, BFS 기초

3. 구현

# graph의 형태는 dict
# key값 = 특정 node
# value값 = 해당 node에 접한 node들의 리스트
# 알아둘 것 : list.extend는 list 끝에 가장 바깥 iterable의 모든 요소를 추가한다

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

1. DFS

# 방법 1. 
def dfs(graph, root):
    visited = []  #방문한 node를 차례대로 저장할 목록
    stack = []  #방문할 node를 차례대로 저장할 목록
    stack.append(root)
    
    while stack:  #방문할 곳이 없을 때까지 loop
        node = stack.pop()  #queue에서 node 꺼내오기
        if node not in visited:  #해당 node에 아직 방문하지 않았다면
            visited.append(node)  #해당 node를 방문 목록에 추가하고
            queue.extend(graph[node])  #queue에 해당 node의 자식 node를 추가해준다
            
    return visited
    
# 방법 2. 
def dfs(root):
    stack = [root]
    
    while True:
        if len(stack) == 0:
            print('All node searched.')
            return None
        
        node = stack.pop()
        if node == Target:
            print('Target found.')
            return node
        
        stack.extend(children)
        
# 방법 3. 재귀(recursive)
def dfs(graph, start, visited=[]):
    
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
            
    return visited

2. BFS

# 방법 1. 
def bfs(graph, root):
    visited = []  #방문한 node를 차례대로 저장할 목록
    queue = []  #방문할 node를 차례대로 저장할 목록
    queue.append(root)
    
    while queue:  #방문할 곳이 없을 때까지 loop
        node = queue.pop(0)  #queue에서 맨앞 node 꺼내오기
        if node not in visited:  #해당 node에 아직 방문하지 않았다면
            visited.append(node)  #해당 node를 방문 목록에 추가하고
            queue.extend(graph[node])  #queue에 해당 node의 자식 node를 추가해준다
            
    return visited
    
# 방법 2. 
def bfs(root):
    queue = [root]
    
    while True:
        if len(queue) == 0:
            print('All node searched.')
            return None
        
        node = queue.pop(0)
        
        if node == Target:
            print('Target found.')
            return node
        
        queue.extend(children)
        
# 방법 3. deque
# deque는 popleft가 가능 → 시간복잡도가 O(1)
# 그냥 list에서 pop(0)하면 시간복잡도가 O(n)이기 때문에 deque가 유리
from collections import deque

def bfs(graph, root):
    visited = []
    queue = deque()
    queue.append(root)
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
            
    return visited