图中边的密度与顶点数之间的关系
我想了解如何计算密集图和稀疏图的大O。 “Algorithms in a nutshell”说，对于稀疏图，O(E) 是 O(V)，而对于稠密图，O(E) 更接近于 O(V^2)。有谁知道它是如何得出的？
I want to understand how to compute big-O for a dense versus sparse graph.
"Algorithms in a nutshell" says that for sparse graph, O(E) is O(V) and for dense graph O(E) is closer to O(V^2). Does anyone know how is that derived?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
假设图表简单 - 在最坏的情况下每个节点都可以连接到所有
|V|-1其他节点，导致[在非有向图中：]|E| = (|V|-1) + (|V| -2) + ... + 1 <= |V| * (|V| -1) = O(|V|^2)。在有向图中：|E| =|V| * (|V|-1) = O(|V|^2)。密集图的一个很好的例子是 clique - 它具有所有边。
对于稀疏图 - 我们假设连接到每个顶点的边数受常数限制。令该常数为
k。因此：<代码>|E| <= k* |V|，我们得到|E| = O(|V|)稀疏图的一个很好的例子是互联网，其中每个 URL 都是一个节点，每个链接都是一条边。
请注意，如果图形不简单，则无法将
|E|与|V|的任何函数绑定。Assuming the graph is simple - at the worst case every node can be connected to all
|V|-1other nodes, resulting in [in not directed graph:]|E| = (|V|-1) + (|V| -2) + ... + 1 <= |V| * (|V| -1) = O(|V|^2). And in directed graph:|E| = |V| * (|V|-1) = O(|V|^2).A good example for a dense graph is a clique - which have all the edges.
For sparsed graph - we assume the number of edges connected to each vertex is bounded by a constant. Let this constant be
k. Thus:|E| <= k* |V|, and we get|E| = O(|V|)A good example for a sparsed graph is the internet, where every URL is a node and every link is an edge.
Note that if the graph is not simple, you cannot bound
|E|with any function of|V|.它不是派生的，而是定义。在具有自环的全连接（有向）图中，边的数量 |E| = |V|² 所以稠密图的定义是合理的。稀疏图的定义是 O(|E|) = O(|V|)，因此每个顶点的最大边数是恒定的。
请注意，如果边的数量少得多，例如 O(lg |V|)，那么它仍然是 O(|V|)。人们可以想象一种带有 |E| 的“半稀疏”图类。 = O(|V| lg |V|) 或类似的东西，但我个人在实践中从未遇到过这样的类。
It's not derived, it's a definition. In a fully connected (directed) graph with self-loops, the number of edges |E| = |V|² so the definition of a dense graph is reasonable. The definition of a sparse graph is one where O(|E|) = O(|V|), so there's a constant maximum number of edges per vertex.
Note that if the number of edges is much smaller, e.g. O(lg |V|), then it's still O(|V|) as well. One could imagine a "semi-sparse" class of graphs with |E| = O(|V| lg |V|) or something like that, but I personally have never encountered such a class in practice.