c - 需要帮助解决使用 C 中的图形的问题

Question

我正在为一个算法类编写一个 C 项目，我真的需要一些帮助!问题是这样的:

我有一组像这样的名字 N = (James,John,Robert,Mary,Patricia,Linda Barbara) 存储在 RB 树中。从这组名字开始，形成了一系列类似的对:

(詹姆斯，玛丽)(詹姆斯、帕特里夏)(约翰、琳达)(约翰、芭芭拉)(罗伯特、琳达)(罗伯特，芭芭拉)

现在我需要以一种可以形成 n 个子组的方式合并元素，并且约束条件是尊重每个配对并且该组具有最小可能的基数。

对于示例中的夫妇，他们将组成两组(詹姆斯、玛丽、帕特里夏)和(约翰、罗伯特、芭芭拉、琳达)。

任务是返回形成的最大组数以及基数最大的组中男性和女性的数量。

在本例中为 2 2 2

我正在考虑构建一个图，其中每个名称都由一个顶点表示，并且两个顶点仅在配对时才位于边中。然后我可以使用算法(如 Kruskal)来找到最小生成树。对吗？

问题是图不会完全连接。我还需要找到一种方法将名称映射到图的边缘，反之亦然。边可以用字符串索引吗？

非常感谢每一个帮助:)谢谢指教!

Answer 1

您不需要找到最小生成树。这实际上是为了在图中找到仍保持图连接的“最佳”边。换句话说，您并不关心约翰和罗伯特是如何联系的，只关心他们是这样的。

你说问题在于图不会完全连接，但我认为这实际上是重点。如果您按照建议使用对来表示图的边，则连接的顶点将形成您正在查找的组。

在您的示例中，詹姆斯连接到玛丽，詹姆斯也连接到帕特里夏。没有其他人连接到这三个顶点中的任何一个(如果他们这样做了，你就会有另一对包含他们的顶点)，这就是为什么他们形成一个组(詹姆斯，玛丽，帕特里夏)。同样，约翰、罗伯特、芭芭拉和琳达都相互关联。

您的任务实际上是形成图表并找到所有彼此不相交的连接子图。

虽然不是完整的算法，但我希望能帮助您入门。