什么是自然密集图的例子？

Question

图对于模拟现实世界的现象和关系非常有用。

从广义上讲，图数据结构和算法分为两类：

• 那些对稀疏图有用的（例如邻接表，约翰逊算法）
• 那些对密集图有用的（例如邻接矩阵，Floyd-Warshall）。

然而，在我能想到的每一种情况下，现实世界的图都是稀疏的。例如：

1. Web 网络形成稀疏图（每个站点都链接到其他几个站点）
2. 社交网络形成稀疏图（每个人都认识一些其他人）
3. 电气网络形成稀疏图（大多数电路元件仅影响附近的少数其他元件）
4. 道路网络形成稀疏图（每条道路都与其他几条道路相连）

（请注意，“很少”与站点/人员/元素/道路/等的总数相比。）

但是，我从来没有找到用于密集图的算法和数据结构的用例。
我记得遇到过的每张图都证明是稀疏的。

我需要将密集图算法用于哪些现实世界的图？

请注意：是的，我知道每个人都互相认识的一小群人形成了一个密集图，但这不是我要问的那种情况，因为：

1. 社交网络软件从来不是为少数人编写的
2. 任何算法都适用于小数据；不需要密集图算法。

这意味着我也不是在寻找诸如“稀疏图的补充”之类的愚蠢示例。
是的，那些是密集的，但除非你能给我一个实际感兴趣的问题的例子，并且用原始稀疏图无法合理解决，否则这不会回答我的问题。

Answer 1

稀疏图的补充是密集图（想想给定网页未链接到的所有网站）。所以有一个开始。

从我的头顶掉下来...

• 小型社交网络（例如，俱乐部中的人可能与俱乐部中的大多数其他人是 Facebook 好友）
• 图的传递闭包，或至少部分传递闭包（例如朋友的朋友）
• 确实写得很糟糕/紧密耦合的代码（想象一个有向图，其中如果 A 引用 B，则 A 类指向 B 类；可能作为成员、方法的返回值等）

更一般地说，如果您想要更密集的图表，请尝试放宽某些旅行限制。