Кратчайший путь BFS Лемма 22,3 - PullRequest
Новая
       30

Кратчайший путь BFS Лемма 22,3

0 голосов
/ 17 декабря 2018

Сначала обозначение:

Пусть d[v] - это расстояние между корнем дерева BFS и вершиной v

Эта книга гласит следующую лемму:

Во время BFS очередь Q содержит вершины: v_1, v_2, ..., v_r, где

  • v_1 - заголовок Q
  • v_rХвост Q

Тогда:

  1. d[v_r] <= d[v_1] + 1
  2. d[v_i] <= d[v_(i + 1)] для i = 1, 2, ..., r - 1

Я не понимаю первое утверждение.На словах это говорит: последняя вершина v_r, которую BFS добавил в очередь, имеет более короткое расстояние до root, чем первая вершина v_1, которую мы добавили в очередь.Визуально: 

      root
      /  \
    v_1  v_2
    /
   v_3
   /
 v_r

Как это возможно?

1 Ответ

0 голосов
/ 19 декабря 2018

Вы неправильно прочитали утверждение. 

d[v_r] <= d[v_1] + 1

означает, что глубина v_r может быть не больше , чем на единицу больше, чем глубина v_1.v_r может быть на том же уровне дерева BFS или на уровне ниже, но никогда дальше этого уровня.Немного пометив дерево, 

      root
      /  \
    v_a  v_b
    /
   v_c
   /
 v_x

v_x никогда не может быть в очереди одновременно с v_a или v_b, но v_c может.

d[v_r] может быть на меньше , чем d[v_1], если вы поставили в очередь ранее посещенную вершину.

...