3

我正在阅读教科书Introduction to AlgorithmsCLRS我想在 c 中实现mstusingkruskal算法,我想知道的是,我应该使用哪个图形实现,邻接表还是邻接矩阵?edges我认为在使用邻接表时排序并不直观,当edge像这样定义邻接表时,邻接表中的表示令人困惑:

typedef struct tagAdjList
{
    int endPointIndex;
    struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;

在对边缘进行排序时,我想使用一个指针数组来指向上面定义的节点,问题是上面定义的结构找不到start point边缘的,但​​是end point. 所以我改变了这样的结构:

typedef struct tagAdjList
{
    int startPointIndex;
    int endPointIndex;
    struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;

我想问的是:这样定义邻接表可以吗?还是有更好的做法?或者我应该使用邻接矩阵(因为我看到有些人在搜索互联网时使用矩阵实现 kruskal)?为什么?对不起英语不好。任何帮助将不胜感激。

4

2 回答 2

3

为了实现 Kruskal 算法,以何种方式表示图形并不重要,因为您永远不会对属于顶点的边进行排序。相反,您将所有边放入一个数组中,然后按升序对该数组进行排序。

你的图的表示并不重要,只要你可以走它,并将所有边收集到一个数组中(首先,你走图来计算边,然后分配一个足够容量的数组,最后你走再次绘制图形,将指向边缘的指针放入动态分配的数组中)。

一旦指向边缘的指针位于数组中,就对数组进行排序(例如,使用qsort)并运行 Kruskal 算法。您将需要实施不相交集以有效地合并森林;只要你实现链表没有问题,实现不相交集绝对不会给你带来麻烦。

于 2012-12-22T04:01:41.043 回答
0

您提到的第一个结构是(稀疏)图的标准表示。请注意,您还需要一个权重字段。我会将其保留为图形的永久表示,只要它至少是稀疏的。

是的,对于 Kruskal,您需要一个更像后者的结构,因为您需要一个明确的源顶点。我会为 Kruskal 定义一个没有链表的不同结构:

int startPointIndex;
int endPointIndex;
int weight;

您将分配这些结构的数组,用图中的边填充它们,按权重对它们进行排序,然后扫描它们,对端点进行不相交的集合并集。

于 2012-12-23T22:40:22.990 回答