图表对于模拟现实世界的现象和关系非常有用。
从广义上讲,图数据结构和算法分为两类:
然而,在我能想到的每种情况下,现实世界的图表都是稀疏的。例如:
(请注意,“很少”是与站点/人员/元素/道路/等的总数数量相比。)
但是,我从未找到密集图的算法和数据结构的用例。
我记得曾经遇到过的每张图表都变得稀疏。
请注意:是的,我知道一小群人中每个人都互相认识,形成了一个密集的图表,但这不是我要问的那种情况,因为:
社交网络软件从来都不是为少数人编写的
稀疏图的补充是密集图(想想给定网页
从我的头顶...
小型社交网络(例如俱乐部中的人可能与俱乐部中的大多数其他人都是 Facebook 好友)图的传递闭包,或至少部分传递闭包(例如朋友的朋友)
图越密集,它就越接近完整,并且具有加权边的完整图通常更容易表示和简单地思考为方阵,可能会散布一些无穷大或负无穷大来表示缺失“边缘”。 或者,它可能会变得接近完整的二部图,也可以表示为矩阵(只是沿两个轴使用不同标签集的矩阵。)
分配问题