给定一个直接图g=（v，e）什么是建立其交叉边集的有效算法？为什么？
附：这不是家庭作业，我只是在准备我的D&A期末考试，我被这个问题困住了。谢谢！
最佳答案
如果我理解正确的话，你就是在有向图中寻找交叉边，它的两端不是彼此的祖先。在这种情况下，可以修改DFS算法以获得交叉边集由于DFS算法在无向图和有向图中的工作方式相似，您需要做的是记录一个顶点发现的时间和完成的时间，并添加一个将一个顶点的这些值与另一个顶点的值进行比较的函数例如，一个弧e有两个端点u和v。当检查e之后的顶点v的邻居u时，如果u已经被访问并且已经完成（即u已经完成时间），并且u的开始时间小于v的开始时间，则e是交叉边一旦算法发现弧是一条交叉边，您可以将该弧添加到交叉边集，并输出最后的集。