Re: [問題] 資料結構中的DFS（Depth first searchꄠ…
你在考慮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
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
