c++ - C++ 中的图形表示

Question

我正在看一本书 The Design and Analysis of Computer Algorithms通读图形章节，我正在尝试实现 DFS。通过阅读该算法的定义，它说，图 G=(V,E) 将 E 中的边分成两组 T 和 B。如果当我们在顶点 v 时顶点 w 以前没有被访问过，则边 (v,w) 被放置在集合 T 中 考虑边 (v,w) ，否则边 `(v,w) 位于集合 B 中。

基本上他的 DFS 算法会给我新的图形，它将是 G=(V,T)。我想知道如何在 C++ 中实现这一点。

我尝试使用 adjacency list，但我很困惑是否需要存储 list 的 map 的 edges 应该没问题。

Answer 1

在VTK ，边存储在一个 vector 中，它总是存储一对 (v,w)。在这个 vector 附近还有 2 个 vector 的 vector 来存储图节点的边缘和边缘。当添加一条新边时，它被添加到边 vector 中，它的节点(v,w)也被添加到 vector 的入边 vector 和出边 vector 中。