图的 DFS，标记为已访问
我正在为（链接列表）图实现 DFS。
我的图形结构示例： https://i.sstatic.net/8GX7V.png
你可以看，有很多名为“a”的节点。它们在顶点方面是相同的，但在节点方面实际上是不同的。实现 DFS 涉及将“a”标记为在某个时刻已访问过。这看起来很容易，但我希望你能在这里看到我的问题。有许多“a”标记为已访问。我希望我在这里做错了什么。
问题： - 首先将“a”标记为已访问并将其推入堆栈 s。这有效地将第一个邻接链表中的节点“a”标记为已访问，但其他邻接链表中的所有其他节点“a”仍然标记为“未访问”。 - 然后考虑“b”，因为它是“a”的第一个未访问的相邻顶点。将其标记为已访问并将其压入堆栈 s 中。 - 现在我们正在探索“b”。从第二个邻接链表中，与“b”相邻的顶点是“a”，并且该顶点未被访问，因此我们再次将其压入堆栈。错误的！
当然，我可以编写一个 markVisit($vertex) 方法，将所有出现的“a”标记为一次访问，但我认为我在上面的实现中没有正确的方法。感谢您的帮助。
I'm implementing a DFS for a (linked list) Graph.
My graph structure example: https://i.sstatic.net/8GX7V.png
As you can see, there are many nodes named "a". They're the same in terms of vertex but they're actually different in terms of node. Implementing DFS involves marking "a" as visited at some point. This seems easy but I hope you can see my problem here. There are many "a" to mark as visited. I hope I'm doing something wrong here.
Problem:
- First mark "a" as visited and push it onto stack s. this effectively mark node "a" in the 1st adjacency linked list as visited but all other nodes "a" in other adjacency linked lists are still marked as "not visited".
- Then consider "b" as it is the first unvisited adjacent vertex to "a". mark it as visited and push it onto the stack s.
- Now we're exploring "b". From the 2nd adjacency linked list, The adjacent vertex to "b" is "a" and this one is unvisited, so we push it onto the stack again. Wrong!
Of course, I can write a markVisit($vertex) method which mark all occurrences of "a" as visited at once, but I don't think I have the right approach in my implementation above. Thanks for your help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
markVisit($vertex)应该是正确的，你需要记住你已经访问过哪些顶点。 DFS 关注的是顶点，而不是边。markVisit($vertex)should be correct, you need to remember which vertexes you already visited. DFS concerns vertexes, not edges.