同步阅读进度，多语言翻译，过滤屏幕蓝光，评论分享，更多完整功能，更好读书体验，试试 阅读 ‧ 电子书库
图分析
当使用本章的算法时，决定使用邻接表还是邻接矩阵的最重要因素是图是否为稀疏图。算法的性能是和图的顶点数|V|还有边数|E|相关的。和其他算法书一样，我们简化了性能的公式，无论在最好、最坏还是平均情况下，我们都使用V、E的大O记法来表示性能。O(V)表示需要和图中顶点数成直接比例的计算步数。但是图中边的密度也必须考虑。在稀疏图中，O(E)近似等于O(V)，然而在稠密图中，它近似等于O(V2)。
我们将会看到，根据图的结构，一些算法会有两个变种，并且这两个变种的性能不尽相同，一个变种也许执行时间为O((V+E)*logV)，而另外一个是O(V2+E)。哪个更加高效呢？表6-1告诉我们这个答案取决于图G是稀疏图还是稠密图。对于稀疏图来说，O((V+E)*logV)显然更加高效一些，而对于稠密图，O(V2+E)就更加快速了。标记为“均衡图”的条目，这种图的期望性能在稀疏图和稠密图上都是相同的，为O(V2)，在这些图上，边的数目大致等于O(V2/log V)。
请支持我们，让我们可以支付服务器费用。
使用微信支付打赏
