作者turnoff11 (好想打排球)
看板CSSE
標題Re: [問題] 資料結構中的DFS（Depth first searchꄠ…
時間Wed Sep 23 11:56:47 2009
※ 引述《MuadDib (Muaddib)》之銘言：
: 你在考慮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 以此類推...
這樣子看起來
似乎跟所謂的深度沒有太大的關係
都只是在找尋所謂的neighbor
而且都是從數字小到大在搜尋
這樣子如果同樣的例子換成是bfs來算
是不是也是一樣的答案呢？
麻煩大大幫我解釋一下囉
感恩
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.30.170.179
→ dendrobium:BFS => 1 2 3 5 4 6 8 7 差很多 09/23 13:55
推 MuadDib:BFS是neighbor先全部找完才開始找neighbor's neighbor 09/23 20:12
→ MuadDib:DFS是root->neighbor->neighbor's neighbor 一直線找下去 09/23 20:13
→ turnoff11:謝謝大大，我終於明白了~感恩，你們都是大好人 09/24 10:42
→ turnoff11:另外推一個網址，裡面可以使用自己的圖來做BFS和DFS 09/24 10:43