图表对于建模现实世界的现象和关系非常有用。
广义上，图数据结构和算法被分为两类：
- 那些适用于稀疏图（例如邻接表，Johnson算法）
- 那些适用于密集图（例如邻接矩阵，Floyd-Warshall算法）。
然而，在我能想到的每种情况下，现实世界的图都是稀疏的。例如：
- Web网络形成稀疏图（每个站点链接到少数其他站点）
- 社交网络形成稀疏图（每个人认识少数其他人）
- 电气网络形成稀疏图（大多数电路元件只影响附近的少数元件）
- 道路网络形成稀疏图（每条道路链接到少数其他道路）
（请注意，“少数”是相对于总站点/人员/元素/道路等数量而言的。）
然而，我从未发现过需要使用算法和数据结构来处理密集图的用例。
我记得遇到的每个图都是稀疏的。
我需要使用密集图算法的什么样的真实世界图形？
请注意：是的，我知道一个小团体中每个人都互相认识会形成密集图，但这不是我所问的情况，因为：
- 社交网络软件永远不只是为了少数人编写而成。
- 任何算法在处理小数据时都能够很好地工作；没有必要使用密集图算法。
这意味着我也不需要像“稀疏图的补图”这样愚蠢的例子。
是的，它们是密集的，但除非你能举出一个实际感兴趣并且不能用原始稀疏图合理解决的问题的例子，否则那不会回答我的问题。