blocks|key|3033075|text|分析这些问题的一种方法是根据内存和时间复杂度(这取决于您希望访问图形的方式)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3033076|将节点存储为带有指向另一个节点的指针的对象|3033077|3033078|这种方法的内存复杂度是O(n)，因为对象的数量和节点的数量一样多。所需的指针(指向节点)的数量最多为O(n%5E2)，因为每个节点对象最多可以包含n个节点的指针。|unordered-list-item|3033079|访问任何给定节点，此数据结构的时间复杂度为O(n)。|3033080|3033081|存储边权重矩阵|3033082|3033083|矩阵的内存复杂度为O(n%5E2)。|3033084|这种数据结构的优点是访问任何给定节点的时间复杂度为O(1)。|3033085|3033086|根据您在图上运行的算法和有多少个节点，您必须选择一个合适的表示。|3033087|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|Z|8|@]|9|@]|A|$]]|$1|H|3|I|5|G|7|10|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|11|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|12|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|13|8|@]|9|@]|A|$]]|$1|N|3|O|5|G|7|14|8|@]|9|@]|A|$]]|$1|P|3|Q|5|G|7|15|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|16|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|17|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|V|$]]

One way to analyze these is in terms of memory and time complexity (which depends on how you want to access the graph). 

Storing nodes as objects with pointers to one another 

<ul>
<li>The memory complexity for this approach is O(n) because you have as many objects as you have nodes. The number of pointers (to nodes) required is up to O(n^2) as each node object may contain pointers for up to n nodes. </li>
<li>The time complexity for this data structure is O(n) for accessing any given node.</li>
</ul>

Storing a matrix of edge weights

<ul>
<li>This would be a memory complexity of O(n^2) for the matrix.</li>
<li>The advantage with this data structure is that the time complexity to access any given node is O(1).</li>
</ul>

Depending on what algorithm you run on the graph and how many nodes there are, you'll have to choose a suitable representation.

blocks|key|3033113|text|我认为你的第一个例子有点模棱两可--节点是对象，边是指针。您可以通过仅存储指向某个根节点的指针来跟踪这些节点，在这种情况下，访问给定节点的效率可能会很低(假设您想要节点4-如果没有提供节点对象，则可能必须搜索它)。在这种情况下，您还会丢失从根节点无法到达的图的部分。我认为这就是f64彩虹所假设的情况，他说访问给定节点的时间复杂度是O(n)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3033114|否则，您还可以保留一个充满指向每个节点的指针的数组(或hashmap)。这允许O(1)访问给定节点，但会稍微增加内存使用量。如果n是节点数，e是边数，则该方法的空间复杂度为O(n+%2B+e)。|3033115|矩阵方法的空间复杂度将沿着O(n%5E2)的线(假设边是单向的)。如果你的图是稀疏的，那么你的矩阵中就会有很多空单元格。但如果您的图是完全连通的(e+=+n%5E2)，则与第一种方法相比，这种方法更有利。正如RG所说，如果您将矩阵分配为一个内存块，那么使用这种方法也可以减少缓存未命中，这可以使跟踪图形周围的许多边的速度更快。|3033116|对于大多数情况，第三种方法可能是最有效的空间-+O(e)+-但会使查找给定节点的所有边成为O(e)的苦差事。我想不出哪种情况下这是非常有用的。|3033117|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

I think your first example is a little ambiguous — nodes as objects and edges as pointers. You could keep track of these by storing only a pointer to some root node, in which case accessing a given node may be inefficient (say you want node 4 — if the node object isn't provided, you may have to search for it). In this case, you'd also lose portions of the graph that aren't reachable from the root node. I think this is the case f64 rainbow is assuming when he says the time complexity for accessing a given node is O(n).

Otherwise, you could also keep an array (or hashmap) full of pointers to each node. This allows O(1) access to a given node, but increases memory usage a bit. If n is the number of nodes and e is the number of edges, the space complexity of this approach would be O(n + e).

The space complexity for the matrix approach would be along the lines of O(n^2) (assuming edges are unidirectional). If your graph is sparse, you will have a lot of empty cells in your matrix. But if your graph is fully connected (e = n^2), this compares favorably with the first approach. As RG says, you may also have fewer cache misses with this approach if you allocate the matrix as one chunk of memory, which could make following a lot of edges around the graph faster.

The third approach is probably the most space efficient for most cases — O(e) — but would make finding all the edges of a given node an O(e) chore. I can't think of a case where this would be very useful.

blocks|key|300038|text|好的，如果边没有权重，矩阵可以是二进制数组，在这种情况下，使用二元运算符可以让事情变得非常非常快。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|300039|如果图是稀疏的，那么对象/指针方法似乎更有效。将对象/指针保存在数据结构中，专门将它们诱使到单个内存块中，这也可能是一个好计划，或者是任何其他使它们保持在一起的方法。|300040|邻接表-简单的连接节点列表-到目前为止似乎是内存效率最高的，但也可能是最慢的。|300041|使用矩阵表示法很容易反转有向图，使用邻接表也很容易，但使用对象/指针表示法就不是那么好了。|300042|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

Okay, so if edges don't have weights, the matrix can be a binary array, and using binary operators can make things go really, really fast in that case.

If the graph is sparse, the object/pointer method seems a lot more efficient. Holding the object/pointers in a data structure specifically to coax them into a single chunk of memory might also be a good plan, or any other method of getting them to stay together.

The adjacency list - simply a list of connected nodes - seems by far the most memory efficient, but probably also the slowest. 

Reversing a directed graph is easy with the matrix representation, and easy with the adjacency list, but not so great with the object/pointer representation.

blocks|key|305125|text|还有几件事需要考虑：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|305126|305127|矩阵模型通过将权重存储在矩阵中，使其更容易用于具有加权边的图。对象/指针模型需要在并行数组中存储边权重，这需要与指针数组同步。|ordered-list-item|305128|对象/指针模型与有向图一起工作比无向图更好，因为指针需要成对维护，这可能会变成unsynchronized.|305129|305130|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|L|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|M|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|N|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|P|8|@]|9|@]|A|$]]]|J|$]]

A couple more things to consider:

<ol>
<li>The matrix model lends itself more easily to graphs with weighted edges, by storing the weights in the matrix. The object/pointer model would need to store edge weights in a parallel array, which requires synchronization with the pointer array.</li>
<li>The object/pointer model works better with directed graphs than undirected graphs because the pointers would need to be maintained in pairs, which can become unsynchronized.</li>
</ol>

blocks|key|305158|text|正如一些人指出的那样，对象和指针方法存在搜索困难的问题，但对于构建二进制搜索树这样的事情来说，这是非常自然的，因为其中有很多额外的结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|305159|我个人喜欢邻接矩阵，因为使用代数图论中的工具，它们使所有类型的问题变得容易得多。(例如，邻接矩阵的第k次方给出了从顶点i到顶点j的长度为k的路径的数目。在取k次方之前添加一个单位矩阵，以获得长度为<=k的路径的数量。取拉普拉斯矩阵的n-1个次项，以获得生成树的数量……等等。)|305160|但是每个人都说邻接矩阵是内存昂贵的！他们只对了一半:当你的图的边很少时，你可以使用稀疏矩阵来解决这个问题。稀疏矩阵数据结构所做的工作恰好就是保存一个邻接列表，但仍然拥有所有可用的标准矩阵运算，让您两全其美。|305161|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

The objects-and-pointers method suffers from difficulty of search, as some have noted, but are pretty natural for doing things like building binary search trees, where there's a lot of extra structure.

I personally love adjacency matrices because they make all kinds of problems a lot easier, using tools from algebraic graph theory. (The kth power of the adjacency matrix give the number of paths of length k from vertex i to vertex j, for example. Add an identity matrix before taking the kth power to get the number of paths of length &lt;=k. Take a rank n-1 minor of the Laplacian to get the number of spanning trees... And so on.)

But everyone says adjacency matrices are memory expensive! They're only half-right: You can get around this using sparse matrices when your graph has few edges. Sparse matrix data structures do exactly the work of just keeping an adjacency list, but still have the full gamut of standard matrix operations available, giving you the best of both worlds.

blocks|key|300078|text|还有另一种选择:节点作为对象，边也作为对象，每条边同时在两个双向链表中:来自同一节点的所有边的列表和进入同一节点的所有边的列表。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|300079|struct+Node+{
++++...+node+payload+...
++++Edge+*first_in;++++//+All+incoming+edges
++++Edge+*first_out;+++//+All+outgoing+edges
};

struct+Edge+{
++++...+edge+payload+...
++++Node+*from,+*to;
++++Edge+*prev_in_from,+*next_in_from;+//+dlist+of+same+"from"
++++Edge+*prev_in_to,+*next_in_to;+++++//+dlist+of+same+"to"
};|code-block|syntax|javascript|300080|内存开销很大(每个节点2个指针，每个边6个指针)，但是|300081|结点删除O(1)结点插入和结点O(1)边插入(给定指向"from“和"+to”结点的指针)结点删除O(1)边删除(给定pointer)|300082|O(deg(n))结点删除(给定pointer)|unordered-list-item|300083|
|300084|O(deg(n))+|300085|300086|a|300087|300088|300089|300090|300091|该结构还可以表示一个相当一般的图:带循环的定向多重图(即，您可以在相同的两个节点之间有多个不同的边，包括多个不同的循环-从x到x的边)。|300092|有关此方法的更详细解释，请访问here。|offset|length|300093|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/5493656/320726^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|F|4|0|0^^$0|@$1|2|3|4|5|6|7|1C|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1D|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1E|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|1F|8|@]|9|@]|A|$]]|$1|K|3|L|5|M|7|1G|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1H|8|@]|9|@]|A|$]]|$1|P|3|Q|5|M|7|1I|8|@]|9|@]|A|$]]|$1|R|3|-4|5|M|7|1J|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1K|8|@]|9|@]|A|$]]|$1|U|3|-4|5|M|7|1L|8|@]|9|@]|A|$]]|$1|V|3|-4|5|M|7|1M|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|1N|8|@]|9|@]|A|$]]|$1|X|3|-4|5|6|7|1O|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1P|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|1Q|8|@]|9|@$12|1R|13|1S|1|1T]]|A|$]]|$1|14|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]]|15|$16|$5|17|18|19|A|$1A|1B]]]]

There is another option: nodes as objects, edges as objects too, each edge being at the same time in two doubly-linked lists: the list of all edges coming out from the same node and the list of all edges going into the same node.

<pre><code>struct Node {
 ... node payload ...
 Edge *first_in; // All incoming edges
 Edge *first_out; // All outgoing edges
};

struct Edge {
 ... edge payload ...
 Node *from, *to;
 Edge *prev_in_from, *next_in_from; // dlist of same "from"
 Edge *prev_in_to, *next_in_to; // dlist of same "to"
};
</code></pre>

The memory overhead is big (2 pointers per node and 6 pointers per edge) but you get

<ul>
<li>O(1) node insertion</li>
<li>O(1) edge insertion (given pointers to "from" and "to" nodes)</li>
<li>O(1) edge deletion (given the pointer)</li>
<li>O(deg(n)) node deletion (given the pointer)</li>
<li>O(deg(n)) finding neighbors of a node</li>
</ul>

The structure also can represent a rather general graph: oriented multigraph with loops (i.e. you can have multiple distinct edges between the same two nodes including multiple distinct loops - edges going from x to x).

A more detailed explanation of this approach is available <a href="https://stackoverflow.com/a/5493656/320726">here</a>.

blocks|key|3033243|text|看看维基百科上的comparison+table吧。它很好地理解了何时使用图形的每种表示。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3033244|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Graph_%2528abstract_data_type%2529#Representations^0|8|G|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Take a look at <a href="http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29#Representations" rel="nofollow noreferrer">comparison table</a> on wikipedia. It gives a pretty good understanding of when to use each representation of graphs.

There are three ways to store a graph in memory:

<ol>
<li>Nodes as objects and edges as pointers</li>
<li>A matrix containing all edge weights between numbered node x and node y</li>
<li>A list of edges between numbered nodes</li>
</ol>

I know how to write all three, but I'm not sure I've thought of all of the advantages and disadvantages of each.

What are the advantages and disadvantages of each of these ways of storing a graph in memory?

Three ways to store a graph in memory, advantages and disadvantages

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

在内存中存储图形有三种方法：节点作为对象，边作为指针包含编号节点x和节点y之间的所有边权重的矩阵编号节点之间的边的列表我知道如何写这三种语言，但我不确定我是否考虑过每种语言的优缺点。在内存中存储图形的每种方法的优缺点是什么？

问在内存中存储图形的三种方法，优缺点
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在内存中存储图形的三种方法，优缺点EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在内存中存储图形的三种方法，优缺点
EN