너비 우선 탐색(Breadth-First Search, BFS)

너비 우선 탐색(BFS)은 그래프를 순회하는 일반적인 기술이다.

그래프 G의 BFS 순회

- G의 모든 정점과 간선을 방문한다.

- G가 연결되었는지 여부를 결정한다.

- G와 연결된 컴포넌트를 계산한다.

- G의 스패닝 포레스트를 계산한다.

- n개의 정점과 m개의 간선이 있는 그래프의 BFS는 O(n+m) 시간이 걸린다. (최단 경로를 찾는 다익스트라 알고리즘은 리니어 타임에 해결이 불가능하다)

- 주어진 두 정점 사이에 최소 간선을 가진 경로를 찾고 보고할수 있다. (DFS는 불가능한 핵심 요소)

 

BFS 알고리즘

- DFS와 마찬가지로 정점과 간선의 label을 설정하고 확인하는 메커니즘으로 사용된다.

Algorithm BFS(G)
	Input Graph G
    Output labeling of the edges
    and partition of the vertices of G
    for all u ∈ G.vertices()
    	u.setLabel(UNEXPLORED)
    for all u ∈ G.edges()
    	u.setLabel(UNEXPLORED)
    for all v ∈ G.vertices()
    	if v.getLabel() == UNEXPLORED
        	BFS(G,v)
            
 Algorithm BFS(G,v)
 	L0 <- new empty sequence // queue.
    L0.insertBack(s)
    s.setLabel(VISITED)
    i <- 0
    while ㄱLi.empty()
    	Li+1 <- new empty sequence
        for all v ∈ Li.elements()
        	for all e ∈ v.incidentEdges()
            	if e.getLabel() == UNEXPLORED
                	w<-e.opposite(v)
                    if w.getLabel() == UNEXPLORED
                    	e.setLabel(DISCOVERY)
                        w.setLabel(VISITED)
                        Li+1.insertBack(w)
                    else
                    	e.setLabel(CROSS)
        i<- i+1

BFS의 속성

1. BFS(G,s)는 Gs의 모든 정점과 간선을 방문한다.

2. BFS(G,s)로 label된 discovery edge는 Gs의 스패닝 트리 Ts를 형성한다.

3. Li의 각 정점 v에 대하여 Ts의 경로 s부터 v까지 i개의 간선을 가지고, Gs에서 s부터 v까지 모든 경로는 적어도 i개의 간선을 가짐.

 

Performance(성능)

- 정점과 간선의 label을 설정하고 확인하는 데 O(1) 시간이 걸린다.

- 각 정점은 두번의 label이 발생(한번은 UNEXPLORED , 한번은 VISITED)

- 각 간선은 두번의 label이 발생(한번은 UNEXPLORED, 한번은 DISCOVERY or CROSS)

- 각 정점은 Li 시퀀스에 한 번 삽입된다.

- incidentEdges() 메소드는 각 정점에 대해 한번 호출된다.

- 그래프가 인접 리스트 구조로 표현 될 경우 BFS는 O(n+m) 시간이 걸린다.