在图中访问边

我正在使用DFS算法，并且希望将每个边标记为已访问，方法是查找节点并将其替换为一些标记，但如果将邻接列表设置为存储与访问的节点相对应的值，这会增加查找时间。矩阵会占用大量空间。什么是最好的算法呢？在图中访问边

2017-01-14 idk

你需要记录边缘被访问？为了让你迭代两次边，你需要两次遍历同一个节点。跟踪访问节点应该更简单。你究竟想要做什么？ –

@ A.Sokol我正在访问一个边缘，我需要记录它，所以我不会再访问，虽然我会如果这样的情况存在1-> 2 && 2-> 1.我需要打印的顺序在哪我访问边缘，所以我需要存储它们。 – idk

那么你为什么不随意打印呢？ – CodingYoshi

你只需要维护一组顶点对。例如Java HashMap<Pair<Vertex, Vertex>>。在Python中，包含2元素元组的Set。

边缘的访问发生在您枚举刚发现的新顶点的后代并将它们添加到DFS堆栈中。如果您使用的是递归DFS，那么就像您对每个后代进行递归调用一样。这里的堆栈版本：

dfs(graph) 
    visitedVertices = \emptyset 
    visitedEdges = \emptyset 
    // Try all vertices as search roots 
    for each vertex r in graph 
    push r onto empty stack 
    while notEmpty(stack) 
     u = pop stack 
     if u not in visitedVertices 
     add u to visitedVertices 
     foreach v such that u->v is in graph 
      add (u,v) to visitedEdges // Visit the edge 
      push v on stack

说了这么多，我不知道你为什么要这么做。正确实施DFS自然而然地遍历每个边缘一次。您可以通过查看上面的算法来证明这一点。访问(u,v)只有在以前从未访问u时才有可能。

也许你有一些其他的线程正在看搜索进度，或者实际上是在你访问时向边缘添加其他信息？

来源

2017-01-16 19:44:35 Gene

我想通过重定向边缘来创建图欧拉电路，而Fleury算法对于我的约束来说太复杂（耗时），我不能去除边缘并再次应用dfs来检查它是否是桥接。您是否认为上述算法在我尝试多次访问节点的情况下失败？如果1-> 2被标记为边2-> 1仍然是可能的，因为它不在标记的边上，但是会产生边和无向边？ – idk

@idk对不起，我不明白你在问什么。 – Gene

给定一个失真的欧拉电路意味着边缘已经重新排列，我想通过重定向已经放置错误顺序的边缘来重新生成欧拉电路来制作图欧拉电路。 – idk

在图中访问边

回答

相关问题