[python] 알고리즘 - 너비 우선 탐색 / BFS(Breadth First Search)

너비 우선 탐색(BFS)

(레이아웃이 PC 에 최적화 되어있습니다.)

 

출처: https://practice.geeksforgeeks.org/problems/difference-between-bfs-abd-dfs

 

BFS 알고리즘은 탐색하는 노드가 속한 레벨을 전부 탐색하고 다음 레벨로 넘어간다. 즉 형제 노드를 전부 탐색하고 자식노드로 내려간다. DFS의 경우 큐와 스택 두가지를 활용했는데, BFS는 큐로 구현한다.

 

 

위 그래프를 딕셔너리 형태로 표현하면 다음과 같다.

 

graph = dict()

graph[0] = [1, 2]

graph[1] = [0, 3, 4]

graph[2] = [0, 5, 6]

graph[3] = [1]

graph[4] = [1]

graph[5] = [2]

graph[6] = [2]

 

 

 

res는 최종적으로 반환할 리스트이며 visit은 탐색할 노드들이 담길 리스트다.

 

 

가장 먼저 시작 노드인 0이 res 리스트에 추가된다. 

다음으로 0에서 탐색 가능한 1, 2가 추가된다.

 

 

 

 

DFS와는 반대로 DFS는 가장 앞에서부터 데이터를

추가한다. 따라서 1이 res에 추가되고 1에서 탐색

가능한 모든 노드가 2뒤에 붙는다.

 

 

2가 res에 추가되고 2에서 탐색 가능한 모든 노드가 visit에 붙는다.

 

 

 

 

이때 0은 이미 res에 존재하므로 무시하고 3이 추가된다. 3에서 탐색 가능한 모든 노드가 visit에 추가된다. visit에 데이터가 없을 때까지 반복한다.

 

 

 

파이썬의 경우 pop메서드의 파라미터를 0으로 주면 DFS와 동일한 코드에 0만 추가해서 BFS로 쓸 수 있다.

#BFS
def bfs(graph, start):
    result, visit = [], []
    visit.append(start)
    
    while visit:
        node = visit.pop(0)
        if node not in result:
            result.append(node)
            visit.extend(graph[node])
    
    return result       


#Test Code
graph = dict()
graph[0] = [1, 2]
graph[1] = [0, 3, 4]
graph[2] = [0, 5, 6]
graph[3] = [1]
graph[4] = [1]
graph[5] = [2]
graph[6] = [2]

bfs(graph, 0)

 

 

만약 pop 메서드를 쓰지 않고 구현해야하는 경우 큐를 직접 구현해서 사용할 수도 있겠지만 아래처럼 del 을 이용해서도 구현할 수 있다.  *단 노드가 이미 res에 존재하는 경우도 생각해줘야 한다. pop 메서드는 데이터를 불러오면서 삭제까지 하기 때문에 큐와 스택의 역할을 대신했다.

#BFS
def bfs(graph, start):
    result, visit = [], []
    visit.append(start)
    
    while visit:
        node = visit[0]
        if node not in result:
            result.append(node)
            visit.extend(graph[node])
            del visit[0]
            
        else: 
            del visit[0]
    
    return result