检测图中的相互边缘 [英] detecting mutual edges in a graph

问题描述

我有一个图的邻接列表表示形式，但它不是对称的，即.如果节点A具有B的边缘，则B具有带有A的边缘并不正确.我想这将是一个有向图(有向图).

I have an adjacency list representation of a graph but it is not symmetric i.e,. if a node A has an edge to B, it is not true that B has an edge with A. I guess this will be a directional graph (digraph).

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

What is a good way to detect all the bidirectional paths from a node. I know I can use DFS to detect the paths from a node to another nodes of the graph. I guess what I am looking for is a bidirectional DFS where only the bidirectional edges are taken into account.

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

So one way to do that is to look at the neighbour for a node and figure out if this is a bidirectional relationship. However, for this I will need to go through all the immediate connections of this neighbouring node and see if the first node is also a connection and if yes, to continue with the recursion. I wonder if this is an efficient way to do this?

推荐答案

使用相当标准的邻接集"表示形式，您可以使用某种类型的集合数据结构(基于哈希或基于树的形式)代替列表来表示从节点出来的边，您只需查询图中是否存在边的反向版本.从邻接列表表示形式构建邻接集表示形式是很直接的.

With a fairly standard "adjacency set" representation, where you use some sort of set data structure (hash- or tree-based) instead of lists to represent the edges coming out of a node, you can just query whether the reversed version of an edge exists in the graph. Building an adjacency set representation from an adjacency list representation is straightfoward.

或者，您可以构建一组图形中所有边的集合，然后从图形中未包含其反向版本的边中过滤出边缘.如果在另一种方法中不再使用邻接集表示形式时，这会更方便.如果要降低内存使用量，则可以在构建集时从图中删除边，如果在图中找到了它们的反向版本，然后在集中(如果它们在集合中)而不是反向版本时，可以从图中删除边.不是.

Alternatively, you can build one set of all the edges in the graph and then filter edges out of the graph whose reversed version isn't in the set. This can be more convenient if you wouldn't have any further use for the adjacency set representation after using it in the other approach. If you want to keep memory usage down, you can remove edges from the set while building it if you find their reversed version in the graph, and then remove edges from the graph afterward if they're in the set instead of if their reversed version isn't.

这篇关于检测图中的相互边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！