| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нахождение мостов в графе |
| Автор: i... 5.10.2004, 14:37 |
| Две задачки с графами решил, а эту... Помогите, пожалуйста, кто чем может. Мостом графа назовем такое ребро, удаление которого увеличивает число компонент связности графа. Найти: все мосты заданного графа. |
| Автор: LSD 5.10.2004, 18:11 |
| Если задача чисто теоретическая то можно так: Возьмем любую пару точек A и B, и построим все возможные пути, без циклов из A в B. Если некое ребро будет входить в все пути, то это мост. Перебрав все возможные пары A и B, найдем все мосты. Для практического применения этот алгоритм не оптимален. |
| Автор: 3,14 6.10.2004, 09:08 |
| Это вариант для связанного графа: Перебираем все возможные разбиения мн-ва вершин графа на два различных мн-ва: 1) Если для какого-то разбиения найдено два различных ребра из одного мн-ва в другое - пееходим к следующему разбиению 2) Если такое ребро только одно, то оно и будет мостом Для несвязанного графа - разбиваем его на компоненты связанности, и к каждой из них применяем этот алгоритм Вообще у моста есть замечательное св-во - оно не содержится не в одном цикле, может кому удасться им воспользоваться, я, увы, не смог  |
| Автор: GePo 6.10.2004, 22:37 |
| Вроде этот алгоритм есть в книге Липского. Решается поиском в глубину. При очередном шаге будем увеличивать текущее время и присваивать его вершине. После всех вызовов из данной вершины запишем минимальное время вершины, которую мы смогли лостигнуть из данной. Если оно равно времени нашей вершины, то ребро из данной вершины и предка в дереве поиска в глубину и есть мост. |
| Автор: 3,14 6.10.2004, 22:52 | ||
Если ты имеешь ввиду книгу: "Комбинаторика для программистов", то в ней я этого алгоритма не нашёл, но может просто прогладел, вот ссылка на оную книгу : ftp://www.scientific-library.net/pub/data/vol2/archive/lipskii.djvu |
| Автор: GePo 8.10.2004, 17:30 |
| Начинаешь читать Липского со страницы 95, раздел 2.6 и читаешьесь раздел. Понимаешь, как находять точки сочленения, а мосты - читаешь, что я написал - будет понятно потом |
| Автор: maxim1000 10.10.2004, 20:23 |
| подумал я тут недавно над этой задачкой, вроде нашел один не очень долгий способ, в котором используется то, что мост не входит ни в один цикл, только вместо цикла я рассматриваю два различных пути, соединяющих две точки для начала: 0. выберем одну вершину (от фонаря) 1. припишем каждой вершине свойство - расстояние до выбранной точки (будем заполнять постепенно, сначала у выбранной точки 0, у остальных (-1)) и номер вершины, откуда в эту приходит минимальный путь 2. припишем каждому ребру свойство - пройдено/не пройдено (сначала все будут "не пройдены"), и "является/нет составной частью какого-нибудь цикла (сначала у всех будет "не является") --- далее будем действовать по такому алгоритму: 1. смотрим на точки, до которых мы добрались на предыдущем шаге (сначала это будет одна выбранная точка) 2. смотрим на все ребра эти точек, которые мы еще не проходили 3. смотрим на точки на концах этих ребер 4. далее есть два варианта: 4.1. точка еще не обрабатывалась (расстояние равно -1), тут все просто даем ей расстояние n+1 4.2. точка уже проходилась - значит, мы обнаружили цикл, надо его пометить, помечаем таким образом: идем по двум путям (минимальному и только что найденному) до точки их раздвоения и помечаем их ребра "входящими в цикл" 5. повторяем все, пока не обработаем все вершины 6. те ребра, которые не помечены как "входящие в цикл" и есть мосты честно говоря, не проверял его на сложных примерах, а так - вроде бы работает плюс этого алгоритма в том, что за один проход обнаруживаются все мосты в графе... |