你在考虑graph的时候不能以tree的角度去看 graph是没有深度的 而graph和tree最大的不同就是graph有cycle/loop而tree没有 所以你实作的时候需要mark的机制来避免重复搜寻的无限回圈 所以DFS简单来说 就是选一个点当root 然後搜寻他其中一个neighbor 再从neighbor里面搜寻未被marked/visited的neighbor 不断循环 直到目前的node已经没有未被marked/visited的neighbor 就做backtrack (回到前一个node) 然後继续找neighbor backtrack有很多种做法 像是stack, recursive function(太深可能会记忆体不足), right-threaded binary tree(引线二元树) 等等 以你的例子来说 1是root 也就是起点 先visit root 然後找neighbor 有2, 3, 5 通常这种图都是照数字大小顺序来visit 所以选择visit 2 之後找2的neighbor 就是4 再找4的neighbor 就是8 (这边我看好久才发现他那条线其实是连到8而不是4 画的并不好) 再找8的neighbor 有5, 6, 7 先visit 5 之後发现5没有未visited neighbor 所以又backtrack至8 再找8的neighbor 剩下6, 7 以此类推... ※ 引述《turnoff11 (好想打排球)》之铭言： : 最近在看资料结构 : 对於DFS（Depth first search）深度优先搜寻 : 和BFS（breadth first search）广度优先搜寻有一些疑问 : 希望版上有高手解答一下 : 1、DFS在搜寻时，是以深度为优先考量 : 请问当两个node都是下一层（或者更深的一层）时 : 一定要从最深的那一层开始吗？ : 2、有些图形并没有规则状 : 不像一般的二元树 : 根本看不出那些点是在同一层 : 那此时该如何进行？ : 3、当一个图形要从较深的地方的某个点当开始搜寻的点 : 应该如何进行？ : 4、在http://aikosenoo.pixnet.net/blog/post/8700834里面 : 中间的图形说是用DFS来找 : 为何是从1-2呢？ : 问同事 : 他跟我说是因为转向了 : 如果是这样子 : 那问题又来了 : 转向是随便我们转的吗？ : 这样子那有什麽比较深还是同一层的比较呢？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.64.170.159