c++ - 关于在c++中实现图形的问题

Question

我正在学习用 C++ 实现图形，因此我阅读了 Wikipedia entry发现有两种常用的方法:邻接表和邻接矩阵。我理解邻接列表和邻接矩阵之间的空间权衡。

我有三个问题

1)除了上面列出的两种方法之外，还有其他方法可以实现图形吗？？

2) 使用不同的数据结构有什么区别？？？链表VS vector VS map

3)文章中下面这段话是什么意思

The other significant difference between adjacency lists and adjacency matrices is in the efficiency of the operations they perform. In an adjacency list, the neighbors of each vertex may be listed efficiently, in time proportional to the degree of the vertex. In an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree. On the other hand, the adjacency matrix allows testing whether two vertices are adjacent to each other in constant time; the adjacency list is slower to support this operation.

他们执行的操作的效率指的是什么？什么类型的操作？？？

两个顶点在常数时间内彼此相邻是什么意思，知道两个顶点是否彼此相邻有什么实际用途吗？？？

Answer 1

1. 是的，您也可以使用指向其他节点的指针显式实现它。
2. listS 消耗更多内存且不是随机访问，但元素的句柄(迭代器)在插入和删除时保持有效； vectorS 内存高效，随机访问，但无效句柄(迭代器)在插入和删除时无效； mapS 通常会消耗更多内存，不要迭代得更慢，句柄(迭代器)通常在插入和删除时保持有效；查找子节点可以非常快。这确实是这些容器之间的一般区别，而不是特定于图形的。
3. 明确给出了操作:列出邻居和测试邻接性。两者都具有不同的复杂性，具体取决于图形实现。

两个顶点彼此相邻只是意味着两个节点之间有一条直接边。在恒定时间内执行此操作意味着该操作与每个节点有多少个邻居无关。就实际目的而言:是的，很多。您可能想知道一个城市是否通过直接街道连接到另一个城市。您可能想知道两个顶点在折叠之前是否有边等。

当你在谈论 C++ 时，我强烈建议你看看一些很好的图形库，比如 Boost.Graph或 Lemon .