[컴][알고리즘] BFS breadth-first search

너비 우선 탐색 / bfs /

BFS breadth-first search

vertex s 에서 출발한다.

s 의 adj 는 A, B 이니,
먼저, A 가 level 에 있는지 본다.
A가 level 에 없으니 A에 대한 level (level['A']) 를 set 한다.
그 다음 B 가 level 에 있는지 본다.
B도 level 에 없으니 B에 대한 level (level['B']) 를 set 한다.
그리고 방문했던 A, B는 next 에 저장해 놓는다.
그래서 그 다음에 loop 을 돌 frontier 를 만들게 된다.

frontier 의 각 adj vertex 들을 접근하면서,
각 vertex 가 방문했는지를 level 이 채워져 있는지로 확인한다.
이미 방문한 애들은 그냥 skip 한다.

prarent 는 각 vertex 가 어디서 부터 왔는지를 저장한다. 이것을 거꾸로 하면, path 가 된다.

level = {}
parent = {}

def bfs(s, adj):
    level = {"s": 0}
    parent = {"s": None}
    i = 1
    frontier = [s] # level i-1
    while frontier:
        next = [] # level i
        for u in frontier:
            for v in adj[u]:
                if v not in level:
                    level[v] = i
                    parent[v] = u
                    next.append(v)
        frontier = next
        i += 1     

이 bfs 를 한번 돌리면, 연결된 "하나의 연결된 그래프"의 vertex 들을 전부 visit 하게 된다. 그리고 현재의 연결된 그래프와 연결되지 않은, 나머지 vertex 의 방문을 위해서는 bfs 를 다시 실행해야 한다.

See Also

1. [컴][알고리즘] Depth-First Search DFS, 깊이우선 탐색

References

1. 13. Breadth-First Search (BFS) - YouTube