Re: [問題] 資料結構中的DFS（Depth first searchꄠ…
※ 引述《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
→
09/23 13:55, , 1F
09/23 13:55, 1F
推
09/23 20:12, , 2F
09/23 20:12, 2F
→
09/23 20:13, , 3F
09/23 20:13, 3F
→
09/24 10:42, , 4F
09/24 10:42, 4F
→
09/24 10:43, , 5F
09/24 10:43, 5F
→
09/24 10:44, , 6F
09/24 10:44, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
