Нахождение самого тяжелого ребра в графе, образующего цикл

Учитывая неориентированный граф, мне нужен алгоритм (inO(|V|+|E|)), который найдет мне самое тяжелое ребро в графе, образующем цикл. Например, если мой график выглядит так, как показано ниже, и я запускаю DFS(A), то самым тяжелым ребром на графике будет BC. (*) В этой задаче у меня максимум 1 цикл.

введите здесь описание изображения

Я пытаюсь написать модифицированный DFS, который вернет желаемый тяжелый край, но у меня проблемы.

Поскольку у меня есть не более 1 цикла, я могу сохранить края цикла в массиве и легко найти максимальное ребро в конце цикла, но я думаю, что этот ответ кажется немного беспорядочным, и я уверен, что есть лучший рекурсивный ответ.


recursion graph max algorithm cycle
person sheldonzy    schedule 24.12.2017    source источник
comment
Почему бы не использовать DFS, чтобы найти круг, сломать его, удалив край, а затем снова запустить DFS, чтобы найти самый тяжелый?   -  person dWinder    schedule 24.12.2017
comment
@DavidWinder какой край убрать? приведенный выше график является всего лишь примером, может быть много ребер, которых нет в цикле   -  person DPDP    schedule 24.12.2017
comment
правильно - но вы можете просто изменить DFS, чтобы найти одно ребро в круге (по последнему ребру, которое вы взяли при встрече с уже посещенным узлом) - ›если вы удалите ее, вы должны получить график без круга, и оттуда проблема проста. просто не забудьте сравнить результат DFS с первым извлеченным ребром на случай, если вы выберете самый тяжелый   -  person dWinder    schedule 24.12.2017
comment
@DavidWinder, что посетит второй dfs? насколько я понял из того, что вы сказали, он все равно будет посещать весь график.   -  person DPDP    schedule 24.12.2017
comment
@noJS - еще раз исправьте - вторая DFS посетит весь граф - у вас будет 2 * O (| v | + | e |) для всего решения. А может я не понял вопроса ...   -  person dWinder    schedule 24.12.2017
comment
@DavidWinder ему нужен максимальный вес ребер, которые находятся в цикле (не для всего графа). если только я не тот, кто неправильно понял: P   -  person DPDP    schedule 24.12.2017
comment
Думаю, я неправильно понял. извиняюсь   -  person dWinder    schedule 24.12.2017

Ответы (2)


arrow_upward
3
arrow_downward

Я думаю, что самый простой способ решить эту проблему - использовать структуру данных union-find (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) аналогично алгоритму MST Краскала:

  1. Поместите каждую вершину в свой собственный набор
  2. Пройдите по краям в порядке веса. Для каждого ребра объедините наборы смежных вершин, если они еще не находятся в одном наборе.
  3. Вспомните последнее ребро, для которого вы обнаружили, что его смежные вершины уже были в том же наборе. Это то, что вы ищете.

Это работает, потому что у последнего и самого тяжелого ребра, которое вы посещаете в любом цикле, уже должны быть смежные вершины, соединенные ребрами, которые вы посетили ранее.

person Matt Timmermans    schedule 25.12.2017
comment
Какова будет временная сложность этого алгоритма? O(|E|log|E|) Я думаю? - person sheldonzy; 28.12.2017
comment
Да, потому что вам нужно отсортировать края. - person Matt Timmermans; 28.12.2017

arrow_upward
1
arrow_downward

Используйте алгоритм сильносвязанных компонентов Тарьяна.

После того, как вы разбили свой граф на множество сильно связанных графов, назначьте COMP_ID каждому узлу, который указывает идентификатор компонента, которому принадлежит этот узел (это можно сделать с небольшим изменением алгоритма. Определите глобальное целочисленное значение, которое начинается с 1. Каждый раз, когда вы извлекаете узлы из стека, все они соответствуют одному и тому же компоненту, сохраните значение этой переменной в COMP_ID этих узлов. Когда цикл всплывающего окна завершится, увеличьте значение этого целого числа на единицу) .

Теперь перебираем все края. У вас есть 2 возможности:

  1. Если это ребро связывает два узла из двух разных компонентов, то это ребро не может быть ответом, поскольку оно не может быть частью цикла.

  2. Если это ребро связывает два узла из одного и того же компонента, то это ребро является частью некоторого цикла. Все, что вам осталось сделать, это выбрать максимальное ребро среди всех ребер типа 2.

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

В приведенном вами примере графика COMP_ID будет выглядеть следующим образом:

  • COMP_ID [A] = 1

  • COMP_ID [B] = 2

  • COMP_ID [C] = 2

  • COMP_ID [D] = 2

Edge 10 соединяет COMP_ID 1 с COMP_ID 2, поэтому он не может быть ответом. Ответ - это максимум среди ребер {2, 5, 8}, поскольку все они соединяют COMP_ID 1 с самим собой, поэтому ответ - 8.

person Said A. Sryheni    schedule 24.12.2017
comment
На графике всего 1 цикл, так что я думаю, что ваше решение излишне, не так ли? - person DPDP; 24.12.2017
comment
Ах, извините, я не заметил, что график содержит не более одного цикла: p. Это немного излишне, но должно работать на любом графике. - person Said A. Sryheni; 24.12.2017