图形对于模拟现实世界的现象和关系非常有用。
一般来说，图形数据结构和算法分为两类：
对稀疏图有用的那些（例如adjacency lists，Johnson's algorithm）
对稠密图有用的那些（例如adjacency matrices，Floyd-Warshall）。
然而，在我能想到的每一种情况下，现实世界的图表都是稀疏的。例如：
网络形成稀疏图（每个站点链接到其他几个站点）
社交网络形成稀疏图（每个人都认识其他人）
电网形成稀疏图（大多数电路元件只影响附近的少数元件）
道路网络形成稀疏图（每条道路连接到其他几条道路）
（请注意，“少数”与场地/人员/要素/道路等的总数相比）
然而，我从来没有发现过稠密图的算法和数据结构的用例。
我所记得的每一个遇到的图形都是稀疏的。
我需要使用密集图算法来处理哪些真实图形？
请注意：是的，我知道一小群人人都认识的人组成了一个密集的图，但这不是我要问的那种情况，因为：
社交网络软件从来不是为少数人编写的
任何算法在处理小数据时都能很好地工作；不需要密集图算法。
这意味着我也不会寻找像“稀疏图的补码”这样愚蠢的例子。
是的，这些是稠密的，但是除非你能给我一个例子，说明一个实际感兴趣的问题，而这个问题用原来的稀疏图是不合理的，否则这不会回答我的问题。
最佳答案
稀疏图的补码是密集图（想想给定网页没有链接到的所有站点）。所以有个开始。
从我的头顶…
小型社交网络（例如，俱乐部中的人可能与俱乐部中的大多数人是Facebook朋友）
图的传递闭包，或至少部分（例如朋友的朋友）
编写得非常糟糕/紧密耦合的代码（想象一个有向图，如果A引用B，则A类指向B类；可能作为成员，方法的返回值等）
更一般地，如果你想要更密集的图形，试着放松某些旅行限制。