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

Question

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

    struct connection
    {
       node1;
       node2;
       edge_value;
    }

现在我需要生成相当数量的这些连接，以测试 Kruskal 的情况。Kruskal 的算法并不比这一代人难，可能是因为这是我第一次面对 Graphs。

Answer 1

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

我假设您已经拥有 kruskal 实现（使用此数据结构，您唯一需要做的就是设置一个向量，然后使用适当的函数对该向量进行排序，最后遍历该向量，计算成本为 n日志（n））。

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