그래프 기본 탐색 알고리즘 - BFS, DFS

BFS

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 bfs(graph, start_node):
  # 아래와 다르게 visited를 딕셔너리로 함으로서, 
    visited = {}
    need_visited_queue = []

    need_visited_queue.append(start_node)
    while need_visited_queue:
        node = need_visited_queue.pop(0)
        # 여기서 O(N)에 해당하는 경우를, O(1)로 줄일 수 있다.
        if node not in visited:
            visited[node] = True
            need_visited_queue.extend(graph[node])
    return visited.keys()

data =bfs(graph, 'A')
print(' '.join(data))
# 출력 결과
# A B C H D I J M E G K F L

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 bfs(graph, start_node):
    # 순회를 완료한 값들을 저장할 딕셔너리
    visited= []

    # 순회하기 위해 대기중인 값들
    need_visited = []

    need_visited.append(start_node)
    # 순회가 완료될 때 까지 반복
    while need_visited:
        # 꺼내온 값은 무조건 pop으로 꺼낸다. 그래야 visited에 이미 있던 값도 순회하며 need_visited에서 제거되기 때문.
        node = need_visited.pop(0)
        # 만약 visited에 없다면, visited에 추가하며 graph[node]에 있는 값을 need_visited에 추가하며 지속적으로 순회가 가능하다.
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

    return visited

print(' '.join(bfs(graph, 'A')))
# 출력 결과 
# A B C H D I J M E G K F L

adj_list = [[2,1 ], [3, 0], [3, 0], [9, 8, 2, 1], [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]

N= len(adj_list)

visited = [False] * N

def dfs(v):
    visited[v] = True
    print(v, ' ', end='')
    for w in adj_list[v]:
        if not visited[w]:
            dfs(w)
print('DFS 방문 순서')
for i in range(N):
    if not visited[i]:
        dfs(i)
# 출력 결과
# DFS 방문 순서
# 0  2  3  9  8  1  4  5  7  6

DFS

DFS는 BFS와 달리 스택의 형태를 가진다.

graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'G', 'H', 'I'],
        'D': ['B', 'E', 'F'],
        'E': ['D'],
        'F': ['D'],
        'G': ['C'],
        'H': ['C'],
        'I': ['C', 'J'],
        'J': ['I']
    }
def dfs(graph, start_node):
    visited = {}
    need_visited_stack = []

    need_visited.append(start_node)

    while need_visited:
        node = need_visited.pop()

        if node not in visited:
            visited[node] = True
            need_visited.extend(graph[node])
    return visited

print(' '.join(dfs(graph, 'A')))

graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'G', 'H', 'I'],
        'D': ['B', 'E', 'F'],
        'E': ['D'],
        'F': ['D'],
        'G': ['C'],
        'H': ['C'],
        'I': ['C', 'J'],
        'J': ['I']
    }
def dfs(graph, start_node):
    visited = []
    need_visited_stack = []

    need_visited_stack.append(start_node)

    while need_visited_stack:
        node = need_visited_stack.pop()

        if node not in visited:
            visited.append(node)
            need_visited_stack.extend(graph[node])
    return visited

print(' '.join(dfs(graph, 'A')))
# 출력 결과
# A C I J H G B D F E