c# - 随机邻接表生成器

Question

我目前正在开发一个应用程序，以在我的最后一年项目的图表中找到最大集团。我已经完成了大部分项目，并且刚刚开始测试应用程序。

该应用程序当前使用邻接列表作为输入，我想知道是否有人知道邻接列表随机生成器，以便我可以测试我的应用程序？

非常感谢

Answer 1

这取决于您的随机图模型。最简单的模型是Erdős–Rényi 模型，您可以在其中指定节点的数量和任何给定对之间的链接概率。这很容易生成，但生成的图表不会很有趣，因为它们与现实世界中观察到的大多数网络完全不同。现实世界的网络通常具有幂律度分布和更高的聚类系数。还有一些您可能感兴趣的其他标准模型可以解决这个问题（Watts-Strogatz或Barabási-Albert）。我还使用了本文中描述的 LFR 模型，此处提供了源代码。

Answer 2

如果您根据邻接矩阵而不是邻接列表来考虑图形，则此问题更容易解决。具有m顶点的图可以用mbym矩阵表示，其中每条边如果不存在则为 0，如果存在则为 1。

对于有向图，所有元素都是必需的，但对于无向图，您需要一个上三角矩阵。

获得邻接矩阵后，您可以轻松地将其转换为邻接列表。