Как создать неориентированный граф в C ++?

Question

Мне нужно сгенерировать простой неориентированный граф, чтобы проверить алгоритм моего Крускала на нем.У меня есть структура для всех соединений, сделанная следующим образом:

    struct connection
    {
       node1;
       node2;
       edge_value;
    }

Теперь мне нужно сгенерировать приличное количество этих соединений, чтобы проверить на них Kruskal.Алгоритм Крускала не был таким жестким, как это поколение, возможно, потому что я впервые сталкиваюсь с Графиками.

Answer 1

Ваша структура данных в порядке, потому что вы хотите запустить алгоритм kruskal!

Я предполагаю, что у вас уже есть реализация kruskal (с этой структурой данных единственное, что вам нужно сделать, это настроитьвектор, а затем отсортировать этот вектор с надлежащей функцией и, наконец, пройти через этот вектор, имея вычислительную стоимость n log (n)).

Если вам нужно проверить свой алгоритм, я рекомендую заглянуть на сайт uva.от всей души могу отослать вас к этой проблеме: http://uva.onlinejudge.org/external/113/11354.html Вы можете использовать 3 примера, чтобы проверить, работает ли ваша реализация kruskal ..