14강. 넓이 우선 탐색

[ 목차 ]

1. 트리 탐색의 방법

2. 넓이 우선 탐색

3. 거리 계산

4. 직전정점 그래프

5. 정점의 색 구분

6. 수행과정

7. 수행시간 분석

 

1. 트리 탐색의 방법

1) 넓이 우선 탐색

2) 깊이 우선 탐색

 

2. 넓이 우선 탐색

1) 시작점을 기준으로 동일한 거리에 있는 노드들을 먼저 탐색하는 것

2) 그래프 G(v,e)와 시작점 s가 주어졌을 때 s에서 도달 가능한 모든 간선을 탐색하여 찾는 과정

3) 거리 : 점점 u부터 정점 v까지의 최단 경로에 있는 간선의 수

s와 v의 거리는 2

4) 시작점으로부터 거리를 하나씩 늘리면서 정점을 탐색

5) 그래프 안의 모든 정점을 탐색한 후 종료

 

3. 거리 계산

1) 탐색을 하면서 시작점으로부터 거리를 계산

2) 시작점으로부터의 거리 : u.d = 3

3) 바로 직전 정점 : u.π : t

 

4. 직전정점 그래프

1) 시작점으로부터 각 정점을 도달하기 직전에 들려야 하는 정점으로 만든 하위 그래프

2) 직선정점 그래프는 넓이 우선 탐색 트리

3) 모든 정점이 연결되어 있고 Eπ = Vπ-1

4) Eπ에 포함된 간선을 트리 간선이라고 지칭

 

5. 정점의 색 구분

1) 초기화한 정점 : 흰색

2) 발견된 정적 : 회색

3) 완료된 정점 : 검정, 모든 인접한 정점을 조사한 경우

 

6. 수행과정

1) Q가 비어있는지 확인 : s

2) s를 기준으로 인접한 정점을 확인 : r, w

3) 인접한 정점을 회색으로 칠하고 s로부터의 거리를 입력

4) 프로데세서 정보를 입력

5) Q에 r 등록

6) w 역시 같은 과정 반복

7) s에 인접한 정점 모두 작업이 끝났을 경우 s를 검정으로 색칠

8) 위 과정을 반복

 

7. 수행시간 분석

1) 초기화시간

2) 그래프 탐색 시간 : O(V+E)

  1] 정점은 최대 한 번만 조사

  2] 간선은 최대 두 번 조사