[파이썬 자료구조] 너비우선탐색(BFS, Breadth-First Search)

 

[파이썬 자료구조] 깊이 우선 탐색 (DFS, depth first traversal)

너비 우선 탐색(Breadth-first search, BFS)은 맹목적탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 

cross edge는 재방문을 막기위한 표시임 

1단계. 임의의 점하나를 선택함(예제에서는 A를 선택)

2단계 A와 연결된 점을 방문함 B를 먼저 방문한다고 가정하고 A에서 BCD순서대로 방문

3단계 B에서 인접한 점들을 방문함 C는 이미 방문했던 점이기때문에 BC선을 cross edge로 표현

4단계 C와 인접한 점들을 방문함 이미 방문한 점과의 연결선은 cross edge로 표시

결과적으로 모든 정점을 순회함

파이썬으로 구현해보자

def BFS(g, s, discovered):
 
    level = [s] 
    while len(level) > 0:
        next_level = [] 
        for u in level:
            for e in g.incident_edges(u): 
                v = e.opposite(u)
                if v not in discovered:
                    discovered[v] = e 
                    next_level.append(v) 
        level = next_level 
 
def BFS_complete(g):
    forest = {}
    for u in g.vertices():
        if u not in forest:
            forest[u] = None
            BFS(g, u, forest)
    return forest

g : 입력받는 그래프

forest: 이미 방문한 선분,정점을 딕셔너리로 표시 

16번줄에서 그래프의 한 점을 선택함

방문하지 않은 점이라면 BFS()를 실행

현재의 점을 레벨에 넣음

next_level에는 현재의 점과 연결되어 있는 점들을 넣어줌

한 점에서 인접한 점이 방문하지 한 적이 없던 점이라면 연결된 선분을 discovered 리스트에 넣어줌. 

그리고 다음레벨에 v를 추가해줌