你在考慮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