Поиск простого пути между двумя вершинами в дереве (неориентированный простой граф)

Учитывая две вершины (A и B) и дерево (G) (неориентированный простой граф). Найдите вершины на простом пути между A и B в G. Алгоритм должен работать со сложностью O (V).

например - найти вершины на простом пути между a и b:

d<->k
k<->a
k<->b

ответ должен быть: к

Я попытался изменить BFS для достижения цели, но пока это не работает.

Какие-либо предложения?


algorithm graph-algorithm breadth-first-search
person Rouki    schedule 29.03.2013    source источник
comment
Под простым путем я предполагаю, что вы имеете в виду кратчайший путь?   -  person Sudipta Chatterjee    schedule 29.03.2013
comment
Путь без повторяющихся вершин   -  person Rouki    schedule 29.03.2013
comment
Как ты модифицировал BFS? Если вы сделаете это правильно, вы найдете кратчайший путь в дереве за O(|V| + |E|) = O(|V|) в случае деревьев, поскольку |E| = |В| - 1 на деревьях.   -  person G. Bach    schedule 29.03.2013
comment
@RickyHartmann Я не понимаю. MST дерева — это само дерево.   -  person G. Bach    schedule 29.03.2013
comment
Я понимаю, как найти кратчайший путь от одной вершины к другой с помощью BFS, но как мне собрать вершины на простом пути ТОЛЬКО между двумя вершинами?   -  person Rouki    schedule 29.03.2013
comment
Ммм, думаю, я действительно просто думал о том, чтобы специально выделить путь или все пути в этом случае.   -  person Ricky Hartmann    schedule 29.03.2013
comment
Просто примечание: кратчайший путь в невзвешенном дереве (или даже в дереве с положительными весами ребер) всегда является простым путем.   -  person G. Bach    schedule 29.03.2013

Ответы (1)


arrow_upward
3
arrow_downward

Если проблема заключается в восстановлении пути после того, как вы нашли расстояние, настройте BFS следующим образом: начните с одной из двух вершин, которые вы хотите соединить, выполните BFS. Для каждой обнаруженной вами вершины v сохраните ее предшественницу: если вы обнаружите вершину w через ребро u->w, то предшественником w будет u. После этого вы можете реконструировать путь в обратном порядке, начиная с целевой вершины и переходя от предшественника к предшественнику, пока не достигнете исходной вершины.

Пример:

     J
      \
       \
        A
       / \
      /   \
     B     C
    / \     \
   /   \     \
  D     E     F
             / \
            /   \
           G     H
            \
             \
              I

Если вы вычисляете путь от D до I, то у вас есть следующие предшественники:

pre[I]=G
pre[G]=F
pre[F]=C
pre[C]=A
pre[A]=B        //A was discovered during the BFS via the edge B->A, so pre[A]=B
pre[B]=D

У вас также будут некоторые предшественники, которые не лежат на вашем пути, поэтому они не будут иметь значения во время реконструкции. В примере у вас также будет

pre[J]=A
pre[E]=B
pre[H]=F

но для пути от источника БФС D до цели I вы их не встретите при реконструкции.

Когда вы восстанавливаете путь, начинающийся с I, вы получаете I<-G, затем I<-G<-F и так далее, пока не получите полный путь в обратном порядке.

Если вас интересует только путь к одной цели, вы можете прервать BFS, как только вы обнаружите цель; это не изменит сложность, хотя. Однако, если вам нужны пути ко всем целям из одной исходной вершины, выполните полную BFS; если вы это сделаете, предшественники позволят вам восстановить путь к любой целевой вершине.

person G. Bach    schedule 29.03.2013
comment
У A действительно есть предшественник, я думаю, вы имеете в виду родителя, потому что дерево выглядит укорененным; Я обновлю. - person G. Bach; 29.03.2013
comment
Чтобы лучше визуализировать это, вы всегда можете думать о дереве с корнем в исходной вершине вашего BFS; таким образом вам никогда не придется думать о родительских вершинах. - person G. Bach; 29.03.2013