BFS, DFS

DFS
深度優先検索

1.実装-スタック利用
リストと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
幅優先検索

インプリメンテーション-キュー使用率

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の2つは、必ずしもアクセス順でなければ、リストではなくリストでアクセスを実現する必要がなく、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