BFS + Graph

BFS(너비 우선 탐색)

 

: 경로가 있는지 탐색하는 알고리즘

: 가까운 노드부터 탐색하는 알고리즘

: 주로 queue 사용 

 

=> 최단 거리만을 가지고 있는 경우 사용

 

# 속도를 빠르게 하기 위해 deque를 사용하기도 한다.
from collections import deque

def bfs(graph, start_node):
    visited = []
    queue = list() 

    queue.append(start_node)
    count = 0 

    while queue:
        node = queue.pop(0)

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

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

 

 

Graph

: 노드 와 간선로 표현 

: 트리랑 다르게 순환구조를 가진다.