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

@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 это тоже один из вариантов ответа получается?

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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@-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