Создание простых ребер пути, не содержащихся в BFS - PullRequest
Новая
       4

Создание простых ребер пути, не содержащихся в BFS

3 голосов
/ 24 февраля 2011

Прежде всего ... вот в чем проблема ...

Приведите пример ориентированного графа G = (V, E), исходной вершины s в V и набора ребер F дерева, содержащихся в E, таких, что для каждой вершины, содержащейся в V, уникальный простой путь в граф (V, F) от s до v является кратчайшим путем в G, но множество ребер F не может быть получено при запуске BFS на G, независимо от того, как вершины упорядочены в каждом списке смежности.

Теперь ... так как это домашнее задание, я не хочу прямого ответа, но больше идей для вещей, чтобы посмотреть / попробовать. Но вот что я подумала до сих пор ...

Я в основном подумал, что я могу создать граф, который имеет несколько кратчайших путей к определенной вершине. Конечно, один из этих путей будет найден в BFS. Но я могу использовать один из альтернативных маршрутов, чтобы вписаться в F. Тем не менее, часть, которая отбрасывает меня, это «независимо от того, как упорядочены вершины» ... Я не уверен, как включить это в мой процесс. Я пробовал петли, различные потоки разных направлений и пока ничего.

Есть еще идеи?

Ответы [ 3 ]

2 голосов
/ 17 мая 2011 
    3
 s ---- x
 |     /  
1|    / 1
 |   /
 |  /
 y

В случае, если на изображении выше не отображается

Предположим,

E = {((s, x): 3), ((s, y): 1), ((y, x): 1)}

, где два кортежа - это упорядоченные пары с прикрепленными весами.

Набор ребер F = { (s, y), (y, x) } содержит всевершины графа.Кроме того, единственный простой путь, который он содержит от s до x, является кратчайшим путем в графе от s до x.Тем не менее, F никогда не найдет F.

Начиная с s, x и y будут обнаружены и помечены серым.Затем, когда y исследован, он найдет только одну другую серую вершину, то есть x, и не добавит ее в качестве потомка в результирующее дерево первой ширины.

1 голос
/ 09 апреля 2013

Вопрос старый, но я отправляю другой ответ, потому что его просматривали много раз.Это вопрос 22-2.6 в книге «Алгоритмы Кормена / Лейзерсона / Ривеста / Штейна», и, скорее всего, его встретят другие.

Ответы выше предполагают, что график взвешен.BFS может создать ребро, заданное в любом ответе, если график взят невзвешенным.Проблема не говорит о том, что граф является взвешенным, и в Cormen он находится в разделе о невзвешенных графах.

Здесь - решение в невзвешенном случае.Шаги:

  1. Возьмите график, который выходит из источника s в 2 вершины x и y.s имеет степень превышения 2. x и y каждый выходит на a и b и больше нигде.
  2. Ваше дерево, которое недоступно BFS, состоит из s в x, из x в a, затем из s в yи от y до b.

Это работает, потому что a и b имеют одинаковое расстояние от x и y.Если вы сначала поставите x в очередь, то ваш путь через BFS будет от x до a и b.Если вы сначала поставите в очередь y, то ваш путь через BFS будет от y к a и b.В BFS нельзя смешивать и сочетать так, как это делает решение.

1 голос
/ 24 февраля 2011

Я не уверен, стоит ли вам просто найти контрпример или найти алгоритм, работающий на любом данном графике. Найти контрпример не очень сложно, например, 

  0
 / \
1   2
|\ /|
| x |
|/ \|
3   4

Источник 0. Набор ребер F содержит (0,1) (0,2), (1,3), (2,4). F не может быть произведен BFS.

Я не нашел общего алгоритма для какого-либо графика, но, возможно, приведенный выше пример может дать подсказку.

...