Open studyingegret opened 2 months ago
最好加一段文字,演示如果不用visited
会怎样。
在把4和1连接的图中,结果可能是4→1→2→5→4无限循环\ 也有可能是4→1, 1→4, 4→1, 1→4无限循环(如果是无向图或有4→1,1→4两条有向边)
很好的建议!目前这一节主要集中在“how”上,“why”的部分还有所欠缺。
图的复杂性(无论是概念还是 code)比较高,如何做到深入浅出,不引起读者的畏难情绪,我还需要多多思考一下。
我推荐看看Grokking Algorithms这本书,我看过,很喜欢。它举了很多实际的例子,一步一步解释原理以及一些算法是怎么想出来的,既详细又通俗易懂。我觉得给读者讲“一个算法是怎么想出来的”很重要,除非读者非常擅长背代码理解抽象的东西
深度优先遍历 https://www.hello-algo.com/chapter_graph/graph_traversal/#932
演示执行过程的图没有环,不能演示在有环图中
visited
哈希集合防止无限递归(绕圈圈)的作用。(如果图没有环是不需要visited
的)比如可以把4和1连接,演示步骤5和6之间加一步:“顶点4的邻接节点1已在visited中(表示已访问),跳过”
注: 一开始没看到是无向图,如果是无向图那么用
visited
是必要的,但是演示有环的情况仍然是有价值的