Помогите, пожалуйста, задача по графам
Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными вершинами и отлична от каждой из них.
Если у кого-то есть уже решение - отпишитесь. Я не знаю, как находить все пути (не кратчайшие) между заданными вершинами.
Если у кого-то есть уже решение - отпишитесь. Я не знаю, как находить все пути (не кратчайшие) между заданными вершинами.
Забыла сказать, реализовать нужно на Си. И классы подключать нельзя :(
По очереди выбрасываем из начального графа каждую из вершын кроме заданых и проверяем на досягаемость между задаными. Если досяжности нет - нашли результат.
Перед выбрасыванием следующей вершыны востанавливаем предыдущую.
Перед выбрасыванием следующей вершыны востанавливаем предыдущую.
Мы таким образом (если честно, сомнительным, как мне кажется) найдём только один путь. А нужно все. и потом сравнить и т.д.
Нужно как-то от заданной находить смежные вершины, и уже от них строить пути, каким-то образом исключая возвращение назад, до другой заданной....
как это реализовать? :(
Нужно как-то от заданной находить смежные вершины, и уже от них строить пути, каким-то образом исключая возвращение назад, до другой заданной....
как это реализовать? :(
Нам не нужно находить все пути. Нам нужно найти такую вершыну без которой все пути розвалятся. (Что я выше и написал)
а то, что таких вершин может быть несколько? получается, все нужно все вершины проверять всё равно?
Цитата: nyanechka
а то, что таких вершин может быть несколько? получается, все нужно все вершины проверять всё равно?
Я не знаю оптимльно ли мое предложение, но помоему быстрее пустить волну N (количество вершын) раз чем находить все пути коих может быть значительно больше, а потом их сравнивать.
Ваше предложение мне очень нравится. :)
и искать все пути - тот ещё геморрой, простите за грубость!
ещё бы это реализовать. Попробую)
Спасибо))
и искать все пути - тот ещё геморрой, простите за грубость!
ещё бы это реализовать. Попробую)
Спасибо))
Цитата: nyanechka
простите за грубость!
Да что вы. Ето просто конструктивный спор по теме :)