检测图中的相互边缘

Question

我有一个图的邻接列表表示，但它不是对称的，即，。如果节点A的边缘为B，则B与A的边缘不对。我想这将是一个方向图（二叉图）。

什么是检测节点中所有双向路径的好方法。我知道我可以使用DFS来检测从节点到图的另一个节点的路径。我想我正在寻找的是双向DFS，其中只考虑了双向边缘。

因此，一种方法是查看节点的邻居并找出这是否是双向关系。但是，为此，我需要遍历此相邻节点的所有直接连接，并查看第一个节点是否也是连接，如果是，则继续递归。我想知道这是否是一种有效的方法？

Answer 1

使用相当标准的“邻接集”表示法，您可以使用某种集合数据结构（散列或基于树）而不是列表来表示从节点出来的边，您可以查询图形中存在反转的边缘版本。从邻接表表示中构建邻接集表示是很直接的。

或者，您可以在图形中构建一组所有边，然后从图的反转版本不在该组中的图中过滤边。如果在其他方法中使用邻接集表示形式后没有任何其他用法，这可能会更方便。如果你想减少内存使用量，如果你在图中找到它们的反转版本，那么你可以在构建它的同时删除边上的边，然后如果它们在该集中而不是在它们的反转版本中，则从图中删除边不是。