Всем привет! В общем тут такое дело, дали курсач, в котором нужно открывать графы в FI-представлении, отображать их графически + матрицу смежности. Последующая работа ведется именно с этой матрицей. Затем идет предобработка (мне лично попалась изичная - удаление петель), а затем сравнение по определенной характеристика. Мне попалось сравнение наибольшего количества дуг, удаление которых оставит граф связным. Так вот в чем загвоздка, я вроде бы в голове сообразил как это сделать, но алгоритм получается слишком громоздкий (перебор каждой последовательности ребер + запись в массив итого удаленных ребер в каждой последовательности + еще и на каждом этапе сверять, остался ли граф связным через поиск в глубину). Есть ли у кого идеи, как упростить это дело или мб алгоритм есть специальный для этого?

Кратко: нужен алгоритм получения наибольшего количества дуг орграфа, которые все еще оставляют его связным (на сколько я понял, имеется в виду сильно связным). На кибер форум писал, но там отписали мол почитай книжки (я ж б**ть такой тупой и не просматривал их, не гуглил в разных местах :/). Вроде бы нашел что-то связанное с вычислением макс. потока, но не уверен, то ли это (ибо о потоках еще лекций не было, хз что да как). Срочно нид хелп, все сделал, кроме этой херни :/

так вам что сделать надо? Не понятно. что вы на входе имеете, что должны выдавать на выходе?

Потом сначало реализуйте, расчитайте стоимость алгоритма, а там уже будет видно, где можно оптимизировать, а то абстрактно тяжело расуждать. Без наличия кода, можно только гадать, что у вас там происходит.

"Преждевременная оптимизация - корень всех зол"

Вы начали оптимизировать без наличия самого алгоритма, это сферический конь в вакууме. Мы не можем знать, что у вас в голове.

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

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

Ну а собственно результат GetEdgeCount(matrix) - GetNeededEdges(matrix) и является тем самым максимальным кол-вом ребер, удаление которых оставит граф сильно связным. По идее