在C语言中实现Kruskal算法的邻接表或邻接矩阵

Question

我正在阅读《算法导论》这本教材，也被称为CLRS，我想用C语言实现使用Kruskal算法的mst，我想知道应该使用哪种图形实现，邻接表还是邻接矩阵？我认为在使用邻接表时对edges进行排序不直观，在定义邻接表时edge的表示方法令人困惑，如下所示：

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

在对边进行排序时，我希望使用一个指向上述节点的指针数组，但问题是上述定义的结构体无法找到边的起始点，只能找到终止点。因此，我将结构体更改为以下形式：

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

我想问的是：这样定义邻接表可以吗？还有更好的实践方法吗？或者我应该使用邻接矩阵（因为我在网上看到一些人在搜索时使用矩阵实现克鲁斯卡尔算法）？为什么？抱歉我的英语不太好，感谢您的帮助。

- toolchainX

Answer 1

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

只要您可以遍历它并将所有边收集到单个数组中（首先，您遍历图以计算边数，然后分配足够容量的数组，最后再次遍历图，将指向边的指针放入动态分配的数组中），则图的表示不重要。

一旦您的边指针在数组中，就对数组进行排序（例如，使用qsort），并运行Kruskal算法。 您需要实现不相交集合数据结构以有效地合并森林； 只要您没有问题实现链接列表，实现不相交集将不会给您带来任何麻烦。

- Sergey Kalinichenko

---

你的意思是数组包含指向边缘的指针吗？在我理解有限的情况下，我认为你提到的“edge”是我在问题中定义的“struct”。在这个“struct”中没有“startPointIndex”成员，通过使用指针，我如何找到“edge”的起始点索引？遍历整个图形吗？那不是很耗时间吗？ - toolchainX

Answer 2

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

是的，对于Kruskal算法，您需要更像后者的结构，因为您需要一个明确的源顶点。我会定义一个不具有链接列表的不同结构，仅供Kruskal使用：

int startPointIndex;
int endPointIndex;
int weight;

你需要分配一个这些结构体的数组，用图中的边填充它们，按权重进行排序，然后扫描这些结构体，通过合并端点来执行不相交集合。

- Keith Randall