Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

深度优先遍历演示的图建议换成有环的(最好演示不记录已访问节点会怎么样) #1417

Open
studyingegret opened this issue Jul 11, 2024 · 3 comments

Comments

@studyingegret
Copy link

studyingegret commented Jul 11, 2024

深度优先遍历 https://www.hello-algo.com/chapter_graph/graph_traversal/#932

演示执行过程的图没有环,不能演示在有环图中visited哈希集合防止无限递归(绕圈圈)的作用。(如果图没有环是不需要visited的)

比如可以把4和1连接,演示步骤5和6之间加一步:“顶点4的邻接节点1已在visited中(表示已访问),跳过”

注: 一开始没看到是无向图,如果是无向图那么用visited是必要的,但是演示有环的情况仍然是有价值的

@studyingegret
Copy link
Author

studyingegret commented Jul 11, 2024

最好加一段文字,演示如果不用visited会怎样。

在把4和1连接的图中,结果可能是4→1→2→5→4无限循环
也有可能是4→1, 1→4, 4→1, 1→4无限循环(如果是无向图或有4→1,1→4两条有向边)

@studyingegret studyingegret changed the title 深度优先遍历演示的图建议换成有环的 深度优先遍历演示的图建议换成有环的(最好演示不记录已访问节点会怎么样) Jul 11, 2024
@krahets
Copy link
Owner

krahets commented Jul 26, 2024

很好的建议!目前这一节主要集中在“how”上,“why”的部分还有所欠缺。

图的复杂性(无论是概念还是 code)比较高,如何做到深入浅出,不引起读者的畏难情绪,我还需要多多思考一下。

@studyingegret
Copy link
Author

我推荐看看Grokking Algorithms这本书,我看过,很喜欢。它举了很多实际的例子,一步一步解释原理以及一些算法是怎么想出来的,既详细又通俗易懂。我觉得给读者讲“一个算法是怎么想出来的”很重要,除非读者非常擅长背代码理解抽象的东西

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants