如何从节点和弧的数据结构中创建图数据结构？

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