3

我正在阅读教科书Introduction to Algorithms，CLRS我想在 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 回答