BFS 분석

Question

나는 Cormen의 다음과 같은 BFS 기능을 가지고 있습니다.

s에서 v까지의 최단 경로 거리 경로 (s, v)는 정점 s에서 정점 v까지의 경로에서 최소 모서리 수로 정의됩니다. 또는 s에서 v까지의 경로가없는 경우 A 길이로의 경로 (들, V) (V)까지의 행은 (S)으로부터 V까지 최단 경로로 알려져있다.

다음 표제어 주어진다

G = (V, E)가하자 방향성 또는 방향성 그래프, s가 임의의 정점 인 V에 속한다고합시다. 그런 다음 모든 에지 (u, v) E에 대해

경로 (s, v) < = 경로 (s, u) +1. 우리가 <을 가지고 왜

내 질문은 우리가 <을 필요로하는 이유 중 하나가 = 나에게 하나 scenrio를 알 수 있습니다 "="괜찮아 내가 가르쳐, 위의 공식에 =입니까?

하자 G = (V, E)를 직접 또는 무향 그래프, 그리고 주어진 소스 정점들 속에서 BFS가 G에서 실행된다고 가정 : 이하

는

이마 2 BFS 알고리즘 각 종점 v가 V에 속할 때, BFS에 의해 계산 된 값 d [v]는 d [v]> = path (s, v)를 만족한다.

증명 :

우리는 정점 큐 Q. 배치되는 횟수에 유도를 사용하여 우리 유도 가설이 D 인 [V]> = 패스 (들, v)의 모든 v 및 V에 속하는

유도의 기초는 s가 BFS의 8 번 줄에서 Q에 놓인 직후의 상황입니다.

모든 v에 대해 d [s] = 0 = path (s, s) 및 d [v] = path (s, v)가 V- {s}에 속하기 때문에 유도 가설이 여기에 있습니다.

제 질문은 "큐를 정점에 놓은 횟수에 따라 유도를 사용합니까?"라는 질문에 대한 저자의 질문이 무엇입니까? 귀납적 가설과의 관계는 무엇입니까?

감사!

BFS(G,s) 
1 for each vertex u V[G] - {s} 
2  do color[u] WHITE 
3   d[u] 
4   [u] NIL 
5 color[s] GRAY 
6 d[s] 0 
7 [s] NIL 
8 Q {s} 
9 while Q 
10  do u head[Q] 
11   for each v Adj[u] 
12    do if color[v] = WHITE 
13     then color[v] GRAY 
14      d[v] d[u] + 1 
15      [v] u 
16      ENQUEUE(Q,v) 
17   DEQUEUE(Q) 
18   color[u] BLACK 

Answer 1

첫 번째 질문에 대해서는 세 개의 정점 만있는 완전한 그래프를 고려하십시오. 이 그래프에서 path (s, v) = path (s, u) + 1?