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