c++ - 寻找有向图的最大值

Question

我得到一个 Directed Graph那不是加权的。如果仅沿边的方向行进，如果我得到一个顶点，我想知道是否可以到达所有其他顶点。如果图形是 Complete Graph这是显而易见的。我对图表不完整的情况感兴趣。

就实现而言，我将每个连接存储在一个multimap 中。 multimap key edge tail multimap value 是边头。所以说我有以下对:

• (1, 2)
• (2, 3)
• (1, 4)

在此图中，如果 1 是给定节点，则可以直接或间接到达每个节点。如果将另一对添加到 multimap:(5, 3) 5 将无法从 1 直接或间接到达，除 3 之外的任何节点也无法从 5 到达，因此此图中没有给定节点将能够到达所有其他节点。

我的问题是:如果我对这个图所做的只是测试单个节点是否可以到达所有其他节点，我是否应该向 multimap 添加边以使所有间接连接直接和然后检查是否所有节点都连接到给定节点？或者有更好的方法吗？

Answer 1

所以您将多重映射用作邻接表？您是在问我们如果两个节点可以相互访问是否应该在此列表中插入邻接关系？我强烈建议不要采用这种方法。如果稍后您想执行任何图形遍历，您的结构将被实际上不存在的边污染。

如果您确实需要记住此类信息，请使用单独的结构以实现可达性。