如何在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

回答