1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.
Скрыть объявление

Привет посетитель! У нас на форуме тебе откроются дополнительные разделы, которые скрыты от гостей! А так же ты найдёшь много полезной информации.

Проблема с графами

Тема в разделе "C++ / C# / .NET", создана пользователем Daan Raven, 17 дек 2017.

  1. Daan Raven

    Daan Raven Свой человек Проверенный

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

    gattsu Свой человек Open Source
    Contributor

    Регистрация:
    24 ноя 2015
    Сообщения:
    145
    Симпатии:
    260
    Баллы:
    471
    так вам что сделать надо? Не понятно. что вы на входе имеете, что должны выдавать на выходе?

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

    "Преждевременная оптимизация - корень всех зол"
    Вы начали оптимизировать без наличия самого алгоритма, это сферический конь в вакууме. Мы не можем знать, что у вас в голове.
     
    kick нравится это.
  3. Daan Raven

    Daan Raven Свой человек Проверенный

    Регистрация:
    7 апр 2015
    Сообщения:
    736
    Симпатии:
    334
    Баллы:
    469
    Спросил у своих, подсказали взять алгоритм Дейкстры и переделать его на поиск не только кратчайшего пути, но и вовсе всех путей.
    В принципе вроде как правильно выводит, чуть позже кину исходник для ознакомления, мало ли, кому понадобится, или мб кто-то даст совет по его модернизации.
     
  4. Daan Raven

    Daan Raven Свой человек Проверенный

    Регистрация:
    7 апр 2015
    Сообщения:
    736
    Симпатии:
    334
    Баллы:
    469


    Ну а собственно результат GetEdgeCount(matrix) - GetNeededEdges(matrix) и является тем самым максимальным кол-вом ребер, удаление которых оставит граф сильно связным. По идее :D
     
Похожие темы
  1. JustFM
    Ответов:
    4
    Просмотров:
    782
  2. Ne1s
    Ответов:
    21
    Просмотров:
    1.105
  3. Soanymore
    Ответов:
    4
    Просмотров:
    627
  4. Ne1s
    Ответов:
    6
    Просмотров:
    375
  5. Azrael
    Ответов:
    25
    Просмотров:
    789
Загрузка...