Breadth-First Search

BFS Search Algorithm

def BFS(start):
    Set L_i = [] for i = 1,..,n
    L_0 = {start}
    for i = 0,...,n-1:
        for u in L_i:
            for each v in u.neighbor:
                if v.state = unvisited:
                    mark v as visited, and put in L_i+1

Running Time은 O(n+m)으로 DFS와 같습니다.

Application - Shortest Path

만약 Weight이 걸려 있지 않는 그래프의 경우 시작점으로부터의 최단 거리를 알 수 있습니다.

 

Application - Bipratite Graph

Biparatite Graph란 연결된 노드가 모드 Bipartite한 경우입니다.

 

이 Graph가 만약 Not Bipartite하다면 cycle of odd length를 찾을 수 있습니다.

 

그래서 BFS로 어떻게 Bipartite를 검증할까요?

아까 Visited Node에는 Coloring을 하지 말라고 했는데 Visited Node지만 Neighbor인 Node에 대해서는 색이 같은지 다른지를 알아봄으로써 이를 검증할 수 있습니다.