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

我必须生成简单的无向图，以测试我的Kruskal算法。我对所有的连接，这样制成的结构：如何在C++中生成无向图？

struct connection 
    { 
     node1; 
     node2; 
     edge_value; 
    }

现在我需要生成这些连接的一个体面的数额，以测试Kruskal的就可以了。克鲁斯卡尔的算法并不比这一代强硬，也许是因为这是我第一次面对图表。

2012-03-08 Kajzer

我相当确定，但因为1个节点我有多个连接，节点应该指向节点。 – 111111 2012-03-08 22:11:22

我必须这样做，这是一个分配。 – Kajzer 2012-03-08 22:31:47

@amit：Kruskal的算法通过按值排序无向边，然后使用UNION-FIND数据结构来获取不形成周期的最重边。 – Manuel 2012-03-08 23:20:07

你的数据结构没问题，因为你想运行克鲁斯卡尔算法！

我假设你已经克鲁斯卡尔实现（这种数据结构，你需要做的是建立一个载体，然后进行排序，与合适的函数向量，最后通过矢量走的唯一的事，有n log（n）的计算成本）。

如果你需要测试你的算法，我会建议考虑UVA的网站，从我的头，我可以把你对这个问题的顶部：http://uva.onlinejudge.org/external/113/11354.html你可以使用3例病例进行测试，如果你的克鲁斯卡实施工程..

2012-04-10 21:15:46 fcsc

回答