c++ - 如何在 C++ 中生成无向图？

Question

我必须生成简单的无向图，以在其上测试我的 Kruskal 算法。我有一个所有连接的结构，如下所示:

    struct connection
    {
       node1;
       node2;
       edge_value;
    }

现在我需要生成相当数量的这些连接，以测试 Kruskal 在上面的连接。 Kruskal 的算法没有这一代那么难，也许是因为这是我第一次面对图形。

Answer 1

你的数据结构没问题，因为你要运行kruskal算法!

我假设您已经有了 kruskal 实现(有了这个数据结构，您唯一需要做的就是设置一个 vector ，然后用适当的函数对该 vector 进行排序，最后遍历该 vector ，进行计算n log(n) 的成本)。

如果您需要测试您的算法，我建议您查看 uva 的网站，从我的头脑中我可以向您推荐这个问题:http://uva.onlinejudge.org/external/113/11354.html您可以使用 3 个示例案例来测试您的 kruskal 实现是否有效..