blocks|key|4758491|text|Dense+graph是一个边数接近最大边数的图。稀疏图是一个边数接近最小边数的图。稀疏图可以是。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|4758492|entityMap^0|0|B|P|3|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

Dense graph is a graph in which the number of edges is close to the maximal number of edges.
Sparse graph is a graph in which the number of edges is close to the minimal number of edges. Sparse graph can be a <a href="http://mathworld.wolfram.com/DisconnectedGraph.html" rel="nofollow noreferrer">disconnected graph</a>.

blocks|key|4758519|text|图的整体特征主要是顶点数V和边数E，这两者的关系决定了图是稀疏的还是稠密的(维基页面here)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4758520|选择图形内存表示背后的整个理论是关于确定最佳访问时间与内存占用之间的权衡，考虑到主题域和使用细节。|4758521|通常，您希望有O(1)个访问时间(并因此将图存储为密集邻接矩阵)，除非您不能容忍内存占用，在这种情况下，您选择最合适的稀疏矩阵表示(维基页面here)。|4758522|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Dense_graph|1|http://en.wikipedia.org/wiki/Sparse_matrix^0|16|4|0|0|0|1Y|4|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]]]

Main graph integral characteristics are number of vertices V and number of edges E. The relation of these two determines whether graph is sparse or dense (wiki page <a href="http://en.wikipedia.org/wiki/Dense_graph" rel="nofollow">here</a>). 

The whole theory behind choosing graph in-memory representation is about determining the optimal access time vs memory footprint tradeoff, considering subject domain and usage specifics.

Generally you want to have O(1) access time (and thus store the graph as a dense adjacency matrix) unless you can't tolerate memory footprint, in which case you choose the most appropriate sparse matrix representation (wiki page <a href="http://en.wikipedia.org/wiki/Sparse_matrix" rel="nofollow">here</a>).

blocks|key|4669922|text|顾名思义，稀疏图是稀疏连接的(例如:树)。通常，边的数量是O(n)，其中n是顶点的数量。因此，邻接列表是首选的，因为它们需要每条边的恒定空间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4669923|稠密图是紧密连通的。这里的边数通常是O(n%5E2)。因此，邻接矩阵是首选。|4669924|为了进行比较，让我们假设图有1000个顶点。|4669925|无论图是密集的还是稀疏的，邻接矩阵都需要存储1000%5E2+=+1,000,000个值。|4669926|如果图是最小连通度(即，它是一棵树)，则邻接表需要存储2997个值。如果图是完全连接的，则需要存储3,000,000个值。|4669927|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

As the names indicate sparse graphs are sparsely connected (eg: Trees). Usually the number of edges is in O(n) where n is the number of vertices. Therefore adjacency lists are preferred since they require constant space for every edge.

Dense graphs are densely connected. Here number of edges is usually O(n^2). Therefore adjacency matrix is preferred.

To give a comparison, let us assume graph has 1000 vertices.

Irrespective of whether the graph is dense or sparse, adjacency matrix requires 1000^2 = 1,000,000 values to be stored.

If the graph is minimally connected (i.e. it is a tree), the adjacency list requires storing 2,997 values. If the graph is fully connected it requires storing 3,000,000 values.

blocks|key|4758671|text|在数学中，稠密图是边的数量接近最大边的图。相反，只有几条边的图是稀疏图。稀疏和密集图之间的区别相当模糊，并且取决于上下文。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4758672|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context.

blocks|key|4670096|text|稀疏图-具有相对较少边(通常是边<+%7CV%7C+log+%7CV%7C)的图称为稀疏图。密集图-缺少相对较少的可能边(与完整图相比)的图称为密集图。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4670097|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Sparse Graphs - Graphs with relatively few edges (generally if it edges &lt; |V| log |V|) are called sparse graphs.
Dense Graphs- Graphs with relatively few of the possible edges missing (as compared to complete graph) are called dense graph.

I read it is ideal to represent sparse graphs by adjacency lists and dense graphs by an adjacency matrix. But I would like to understand the main difference between sparse and dense graphs.

What is the distinction between sparse and dense graphs?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我读到用邻接表表示稀疏图，用邻接矩阵表示稠密图是很理想的。但我想要了解稀疏和密集图之间的主要区别。

问稀疏图和密集图的区别是什么？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问稀疏图和密集图的区别是什么？EN