0

我制作了以下节点和弧结构：

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 算法。我无法理解如何利用这两个结构。每个节点都存储其名称和坐标以及有关往返于它的弧的信息。所以我有一个节点集群，但我如何将所有东西链接在一起。这里没有根节点。我应该在我的图表类中添加什么？我已经搜索了邻接列表和矩阵，但不明白如何将我的想法与它们联系起来？请解释

4

1 回答 1

0

您需要定义一个标准来比较两条弧线并确定哪个弧线“更小”。

给定两个节点的坐标，知道如何比较它们。
根据您的标准订购您的弧线。
从一个包含所有节点但没有弧的空图开始。
使用 DisjointSet 结构来维护有关您的连接组件的信息（以避免循环）
将您的弧从小到大添加到图形中，如果创建循环则忽略弧。

Kruskal 算法：http ://en.wikipedia.org/wiki/Kruskal 's_algorithm

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

于 2013-07-18T04:49:33.343 回答