[Section 5] 탐색의 기본 _ 너비 우선 탐색 기법(Breadth First Search)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

너비 우선 탐색 기법은 이전에 배운 트리의 레벨 순회 알고리즘과 아주 유사하다. 그래프에서도 계층을 우선으로 하여 탐색하기 위해서는 큐를 이용해야 하고 때때로 깊이 우선 탐색 기법보다 우수한 성능을 보이기도 한다. 이 BFS 알고리즘에 대해 배워보자. 

1. 너비 우선 탐색의 이해 _ 모든 꼭짓점 노드를 방문하는 방법

다음의 예시 그래프를 참고하도록 하자.

 

예시 그래프

 

 

너비 우선 탐색(Breadth First Search)의 꼭짓점 노드 방문 순서는 다음과 같다.

 

 

BFS 알고리즘 이해

2. 알고리즘 구현 _ 너비 우선 탐색(Breadth First Search)

다음의 예시 코드로 너비 우선 탐색을 구현해보고, 그 개념을 완전히 이해하도록 하자.

 

예시 코드:

def BFSTravel(G,s):
    start = G.getV(s)
    Q=CQ(9)
    Q.enQ(start)
    while Q.length>0:
        current=Q.deQ()
        for i in current.adjacent:
            if i.isV==False:
                i.isV=True
                print(i)
                Q.enQ(i)

def BFS(G):
    for v in G:
        if v.isV==False:
            v.isV=True
            print(v)
            BFSTravel(G,v.getv())

 

코드 결과:

 

코드 결과

 

어떻게 알고리즘이 구현되는지 이해하도록 하자.