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

我有三个问题

1)除了上面列出的两种以外,还有其他方法可以实现该图吗?

2)使用不同的数据结构之间有什么区别?链表VS vector VS映射

3)下一段在文章中是什么意思


efficiency of the operations they perform指的是什么?什么类型的操作???
two vertices are adjacent to each other in constant time是什么意思,知道两个顶点是否彼此相邻是否有实际用途?

最佳答案

  • 是的,您还可以使用指向其他节点的指针来显式实现它。
  • listS占用更多内存,并且不是随机访问的,但是元素的句柄(迭代器)在插入和删除时仍然有效; vectorS是内存有效的随机访问,但是无效句柄(迭代器)在插入和删除时无效。 mapS通常会占用更多内存,不要迭代太慢,句柄(迭代器)通常在插入和删除时仍然有效;查找子节点可以非常快。这实际上是这些容器之间的一般区别,并不是特定于图形的。
  • 明确给出了这些操作:列出邻居并测试邻接关系。两者都有不同的复杂度,具体取决于图形实现。
  • two vertices are adjacent to each other仅表示两个节点之间存在直接边缘。以恒定的时间执行此操作意味着该操作与每个节点具有多少个邻居无关。按照实际目的:是的,其中有很多。您可能想知道一个城市是否通过直达街道与另一个城市相连。在折叠等之前,您可能想知道两个顶点是否具有边。

    当您在谈论C++时,我强烈建议您看一些好的图库,例如Boost.GraphLemon

    关于c++ - 有关在C++中实现图形的问题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/20567609/

    10-11 22:51
    查看更多