Модификации BFS/DFS, чтобы проверить простые пути

Я должен разработать алгоритм, как от BFS или DFS сделать следующее, учитывая G = (V, E), ориентированный граф:Модификации BFS/DFS, чтобы проверить простые пути

Проверьте, есть ли в большинстве один простой путь от s к любой другой вершине u в V. Этот алгоритм должен быть на O (| V | + | E |).

И от предыдущего алгоритма, я должен разработать еще один O алгоритм для проверки, есть ли в самый один простой путь между любыми двумя вершинами у и v (| | V || E).

Надеюсь, вы можете мне помочь! Заранее большое спасибо!

источник

2013-07-07 Stratford

Добро пожаловать на StackOverflow. Что вы пробовали? –

Подсказка: Что делать, если все ребра на пути от s к ˙U являются cut edges (мост)? Что делать, если какой-либо из них не обрезается? :)

Примечание: Мы можем найти все мосты в графе O (V + E) Время

источник

2013-07-07 13:24:28 Fallen

Хорошее решение! Я прочитал ссылку на wiki, но описанный там алгоритм линейного времени я не смог получить. Может быть, это может быть описать это простыми словами? – Aravind

@ Aravind: Вы можете посмотреть [здесь] (http://stackoverflow.com/questions/11218746/bridges-in-a-connected-graph) Кстати, если вам нравится решение, почему бы не проголосовать за него? :) Вот как другой может найти ответ интересный :) Спасибо! – Fallen

Спасибо @MuhammedHedayet !! Это очень полезно. С кодом, который вы опубликовали ранее, я могу найти все мосты, но как определить, существует ли путь между _s_ и любой вершиной, состоящей только из мостов? – Stratford

Модификации BFS/DFS, чтобы проверить простые пути

ответ

Смежные вопросы