关于图的C++

Question

我学习C++实现的图形执行问题，因此我读Wikipedia entry，发现有两种常用的方法：邻接表和邻接矩阵。我理解邻接表和邻接矩阵之间的空间折衷。

我有三个问题

1）是否有其他的方式比上面列出来实现图中的其他两个？

2）使用不同的数据结构之间有什么区别？链表VS矢量地图VS

3）这是什么下面的段落是指文章

邻接表和邻接之间的其他显著差异 矩阵是他们执行的操作的效率英寸在邻接列表中，每个顶点的邻居可以有效地列出 ，在时间上与顶点的度数成比例。在邻接矩阵中，该操作花费的时间与图中顶点的数量 成比例，其可能显着高于 度。另一方面，邻接矩阵允许测试两个顶点是否在恒定时间内彼此相邻; 邻接列表较慢以支持此操作。

efficiency of the operations they perform是指什么？什么类型的操作？

two vertices are adjacent to each other in constant time是什么意思，有什么实际用法知道两个顶点是否相邻？

Answer 1

1. 是的，您也可以使用指向其他节点的指针来显式实现它。
2. listS消耗更多内存并且不是随机访问，但处理（迭代器）元素在插入和删除时保持有效; vectorS是内存有效的随机访问，但无效处理（迭代器）在插入和删除时失效; mapS通常会消耗更多的内存，不会迭代得更慢，处理（迭代器）通常在插入和删除时保持有效;查看子节点可以非常快。这实际上是这些容器之间的一般区别，而不是特定的图形。
3. 这些操作是明确给出的：列出邻居并测试邻接关系。根据图的实现，两者都有不同的复杂性。

two vertices are adjacent to each other只是意味着在两个节点之间存在直接边缘。在恒定时间内这样做意味着操作与每个节点有多少个邻居无关。实际目的是这样的：是的，它们很多。您可能想知道某个城市是否通过直达街道连接到另一个城市。你可能想知道两个顶点在折叠之前是否有边缘等。

当你在说C++时，我会强烈建议你看看一些好的图库，如Boost.Graph或Lemon。