如何從節點和弧的數據結構中創建圖數據結構？

Question

我做了以下節點和弧結構：

struct arc 
{ 
int length; 
string start; 
string end; 

    arc(int k,string s,string e) 
    { 
    this->length = k; 
    this->start = s; 
    this->end = e; 
    } 
}; 

struct node 
{ 
string name; 
double x; 
double y; 
vector<arc> link; 

node(string n,double xx,double yy) 
    { 
    this->name = n; 
    this->x = xx; 
    this->y = yy; 
    } 
}; 

現在我想打一個圖形數據結構，使得我就能實現它Kruskal算法。 我不明白我如何利用這兩個結構。每個節點存儲其名稱和座標以及有關往返於其上的弧的信息。 所以我有一個節點集羣，但我如何鏈接在一起的一切。這裏沒有根節點。我應該添加到我的圖課嗎？ 我搜索了鄰接列表和矩陣，但無法理解如何將我的想法與他們聯繫起來？請好好解釋一下

Answer 1

你需要定義一個標準來比較兩個弧，並確定哪一個是「較小」的。

給定兩個節點的座標，知道如何比較它們。
按照您的標準對弧進行排序。
從所有節點但沒有弧的空圖開始。
使用DisjointSet結構維持有關您的連接部件（避免週期）
從較小的圖添加您的弧線到最大，而忽視了圓弧如果構成一個循環。

克魯斯卡算法：http://en.wikipedia.org/wiki/Kruskal「s_algorithm

DisjointSet：http://en.wikipedia.org/wiki/Disjoint-set_data_structure