Поиск мостов в графе

@DmitryM5 · Регистрация: 27.08.2013

Студворк — интернет-сервис помощи студентам

Доброй ночи,задача состоит в отыскании мостов в графе.
Много где есть в свободном доступе алгоритм примерно такого рода:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
vector<list<int>> G;
int n;//count vertex
vector<bool> used;
vector<int> tin;
vector<int> fup;
int timer;
 
 
//
void IS_BRIDGE(int to,int v) {
    cout<<to<<" "<<v;
}
 
//
void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (list<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
        int to = *it;
        if (to == p)  continue;
            if (!used[to])
            {
                dfs(to, v);
                fup[v] = min(fup[v], fup[to]);
                if (fup[to] > tin[v])
                    IS_BRIDGE(to, v);
            }
            else
                fup[v] = min(fup[v], tin[to]);
        }
    }
//
void find_bridges() {
    timer = 0;
    for (int i=0; i<n; ++i)
        used[i] = false;
    for (int i=0; i<n; ++i)
        if (!used[i])
            dfs (i);
}

"Таким образом, если для текущего ребра (v,to) (принадлежащего дереву поиска) выполняется fup[to] > tin[v], то это ребро является мостом; в противном случае оно мостом не является."

Почему то алгоритм неверно работает,в примере где два моста допустим выводит 1ый мост верно,а 3ой нет.
В чем ошибка может быть?

Добавлено через 8 часов 5 минут
Отпечатался 2ой мост неверно.

@-THE_MASTER666- · 14.11.2014, 10:51

В пейнте нарисуй свой граф и суть вопроса, так ничего не понятно.

@DmitryM5 · 14.11.2014, 17:26 **[ТС]**

Сообщение от -THE_MASTER666-

В пейнте нарисуй свой граф и суть вопроса, так ничего не понятно.

Должно вывести мосты: 2-4; 3-5
Выводит : пустоту
Граф задан таким образом:
8 вершин
0-номер вершины 1 2 3-вершины в которые есть ребро
1-номер вершины 0 2 3-вершины в которые есть ребро
2-номер вершины 0 1 3 4-вершины в которые есть ребро
3-номер вершины 0 1 2 5-вершины в которые есть ребро
4-номер вершины 2 5 6 -вершины в которые есть ребро
5-номер вершины 3 4 7-вершины в которые есть ребро
6-номер вершины 4 7-вершины в которые есть ребро
7-номер вершины 5 6-вершины в которые есть ребро

@DmitryM5 · 14.11.2014, 17:54 **[ТС]**

Если быть точнее программа работает если в графе есть один мост,его и выводит.
Если моста 2 то ничего не выводит.

@-THE_MASTER666- · 14.11.2014, 18:01

Ойй сколько дурацких математических понятий.... Давай по человеческий разрисуем картинку твоего графа:
1. У тебя есть обычный однослойный граф, то есть не гиперграф.
2. Что же в нём есть? В нём есть вершины и рёбра.
Давай вот это вот по проще запишем:
2.1. Есть вершины
2.2. У каждой вершины есть взаимосвязи на другие вершины. Вот это вот:
Имбо

Сообщение от DmitryM5

1 2 3-вершины в которые есть ребро

далеко не всем понятно.

Теперь главный вопрос, ну вот есть у тебя список вершин, у каждой вершины есть список взаимосвязей, каждая взаимосвязь - это просто в данном банальном случае - id другой вершины. То есть всегда известно, с какими другими вершинами связанна какая -то конкретная. Ну и что тут искать? Какие мосты? Ведь вроде и так всё ясно и задано с самого начала.

@SlavaSSU · 14.11.2014, 18:09

-THE_MASTER666-, мост - это ребро, при удалении которого граф станет не связным. на картинке от ТС, кстати, я мостов не вижу!

Добавлено через 52 секунды
DmitryM5, отвечу и тебе сразу, в графе к-ый ты нарисовал, нет мостов.

@-THE_MASTER666- · 14.11.2014, 18:12

Сообщение от SlavaSSU

мост - это ребро, при удалении которого граф станет не связным

Пфф...

Ну тогда мост там, где у вершины только одна взаимосвязь.

@SlavaSSU · 14.11.2014, 18:15

-THE_MASTER666-, сложность задачи в том, что надо найти все мосты.

@DmitryM5 · 14.11.2014, 18:16 **[ТС]**

Сообщение от SlavaSSU

DmitryM5, отвечу и тебе сразу, в графе к-ый ты нарисовал, нет мостов.

Да как я понял действительно на этом графе нету мостов.
Но мне нужно найти эти два ребра(которые красным выделены)значит если я к примеру удалю на время одно из них и запущу поиск моста,то он найдет один мост,и потом проделаю тоже самое аналогично удалив другое красное ребро и запустив поиск моста.
Вопрос в том как определить эти два ребра между компонентами связностями?

@SlavaSSU · 14.11.2014, 18:20

DmitryM5, не понимаю задачу. найти все пары ребер, такие что удалив одно из них из графа, второе станет мостом? или в чем задача?

@DmitryM5 · 14.11.2014, 18:26 **[ТС]**

Сообщение от SlavaSSU

DmitryM5, не понимаю задачу. найти все пары ребер, такие что удалив одно из них из графа, второе станет мостом? или в чем задача?

Предположим у нас есть 2 компоненты связности(выкинули два красных ребра) т.е вершины 0,1,2,3 и 4,5,6,7.
Два красных ребра это так скажем пути из 1-ой компоненты связности во 2-ую т.е. 2-4 и 3-5.
Вопрос как найти эти два пути..

@SlavaSSU · 14.11.2014, 18:37

DmitryM5, найти наимеьшее подмножество ребер, при удалении которых граф станет несвязным. может быть так должна звучать задача? или опять не угадал?

@DmitryM5 · 14.11.2014, 18:40 **[ТС]**

Сообщение от SlavaSSU

DmitryM5, найти наименьшее подмножество ребер, при удалении которых граф станет несвязным. может быть так должна звучать задача? или опять не угадал?

Ну скажем есть две группы вершин,между которыми существует всего два пути(красных ребра как на примере).
Задача в отыскании этих двух путей(красных ребер)...Как то так.

@SlavaSSU · 14.11.2014, 18:43

DmitryM5, а сколько вершин и ребер в графе?

@DmitryM5 · 14.11.2014, 18:46 **[ТС]**

Сообщение от SlavaSSU

DmitryM5, а сколько вершин и ребер в графе?

n-ое количество.

@SlavaSSU · 14.11.2014, 18:53

DmitryM5, странное ограничение. совсем тупое решение пройдет? перебрать пару ребер, удалить их и проверить что получилось 2 компоненты связности.

щас опять посмотрел на рисунок. ребра 4-6 и 5-7 это тоже один из вариантов ответа получается?

@DmitryM5 · 14.11.2014, 19:00 **[ТС]**

Сообщение от SlavaSSU

DmitryM5, странное ограничение. совсем тупое решение пройдет? перебрать пару ребер, удалить их и проверить что получилось 2 компоненты связности.
щас опять посмотрел на рисунок. ребра 4-6 и 5-7 это тоже один из вариантов ответа получается?

Нет эти два не подходят.
Да странно получится,если удалять пару то не выйдет так..хм

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@-THE_MASTER666- Заблокирован
	14.11.2014, 10:51
	В пейнте нарисуй свой граф и суть вопроса, так ничего не понятно. 1

@DmitryM5 Консультант Витте 106 / 86 / 45 Регистрация: 27.08.2013 Сообщений: 1,356 Записей в блоге: 1
	14.11.2014, 17:54 [ТС]
	Если быть точнее программа работает если в графе есть один мост,его и выводит. Если моста 2 то ничего не выводит. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 18:09
	-THE_MASTER666-, мост - это ребро, при удалении которого граф станет не связным. на картинке от ТС, кстати, я мостов не вижу! Добавлено через 52 секунды DmitryM5, отвечу и тебе сразу, в графе к-ый ты нарисовал, нет мостов. 1

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 18:15
	-THE_MASTER666-, сложность задачи в том, что надо найти все мосты. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 18:20
	DmitryM5, не понимаю задачу. найти все пары ребер, такие что удалив одно из них из графа, второе станет мостом? или в чем задача? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 18:37
	DmitryM5, найти наимеьшее подмножество ребер, при удалении которых граф станет несвязным. может быть так должна звучать задача? или опять не угадал? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 18:43
	DmitryM5, а сколько вершин и ребер в графе? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 18:53
	DmitryM5, странное ограничение. совсем тупое решение пройдет? перебрать пару ребер, удалить их и проверить что получилось 2 компоненты связности. щас опять посмотрел на рисунок. ребра 4-6 и 5-7 это тоже один из вариантов ответа получается? 1