[자료구조 및 알고리즘] 너비우선탐색(BFS)

 

BFS(너비우선탐색)는 DFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. BFS는 큐로 구현할 수 있다. BFS는 최단거리를 찾는데 많이 이용된다.

BFS는 다음과 같은 알고리즘으로 작동한다.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 큐에 삽입한다.

아래와 같은 그래프가 있을 때, 이를 BFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 큐에 넣어주는 것이다.

 

출처 : 안경잡이 개발자 네이버 블로그

시작노드 1번을 큐에 넣고 방문처리한다.

출처 : 안경잡이 개발자 네이버 블로그

큐에서 노드 1을 뺀다.(뺀 노드는 위쪽에 표시하였다.) 1과 연결된 노드 중 아직 방문하지 않은 2,3 노드를 큐에 넣고 방문처리한다.

출처 : 안경잡이 개발자 네이버 블로그

큐에서 2를 빼고 2와 연결된 노드 중 3은 이미 방문했으니 4,5를 큐에 넣는다.

출처 : 안경잡이 개발자 네이버 블로그

큐에서 3을 빼고 3과 연결된 노드 중 방문하지 않은 노드인 6,7을 큐에 넣는다.

출처 : 안경잡이 개발자 네이버 블로그

이후, 4,5,6,7이 큐에서 차례로 빠진다.

출처 : 안경잡이 개발자 네이버 블로그

이 같이 BFS로 탐색하면 최종적으로 방문순서는 1->2->3->4->5->6->7

이를 파이썬 코드로 구현하면 아래와 같다.

visit = [False for _ in range(8)]
a = [[] for _ in range(8)]

def bfs(start):
    q = []
    q.append(start)
    visit[start] = True
    while q:
        x = q.pop(0)    # 0번째 원소를 return하고 제거
        print(x)
        for i in a[x]:
            y = i
            if not visit[y]:
                q.append(y)
                visit[y] = True

# 연결리스트 구현
connection = [(1,2),(1,3),(2,3),(2,4),(2,5),(4,5),(3,6),(3,7),(6,7)]
for i,j in connection:
    a[i].append(j)
    a[j].append(i)
bfs(1)

 

참고

• m.blog.naver.com/ndb796/221230944971