🌳 BFS & DFS 視覺化教學

廣度優先搜尋 vs 深度優先搜尋

800ms
未訪問
當前節點
已訪問

🟢 BFS (廣度優先搜尋)

  • 策略：一層一層搜尋，先訪問所有相鄰節點
  • 資料結構：使用佇列 (Queue) - 先進先出
  • 特點：找到的路徑一定是最短路徑
  • 適用：最短路徑問題、層級遍歷
  • 空間複雜度：O(V) - 需要儲存所有同層節點

🔵 DFS (深度優先搜尋)

  • 策略：一路走到底，再回頭探索其他分支
  • 資料結構：使用堆疊 (Stack) - 後進先出
  • 特點：會優先探索深層節點
  • 適用：拓撲排序、路徑查找、迷宮
  • 空間複雜度：O(h) - h為樹的高度
點擊上方按鈕開始演示...

🕷️ 實戰演練：網頁爬蟲為什麼用 BFS？

🟢 使用 BFS 的爬蟲（推薦）

✅ 優點：
  • 平衡探索：不會卡在單一網站太深
  • 禮貌爬取：分散請求到不同網站，避免過載
  • 快速覆蓋：優先獲取廣度資訊
  • 易於控制：可設定深度限制
🎯 實際場景：
  • 搜尋引擎索引網頁
  • 新聞爬蟲抓取頭條
  • 社群媒體爬取
  • 網站地圖生成

🔵 使用 DFS 的爬蟲（問題多）

⚠️ 缺點：
  • 容易卡住：可能一直爬同一網站的深層頁面
  • 伺服器過載：短時間大量請求同一網站
  • 覆蓋不均：花太多時間在單一路徑
  • 可能無限循環：網站內部連結互相指向
🔍 可能的場景：
  • 特定資料深度挖掘
  • 單一網站完整抓取
  • 檔案系統遍歷
  • 需要完整路徑的情況

💡 關鍵洞察：為什麼爬蟲偏好 BFS？

1. 避免「陷入兔子洞」：想像你要調查100個網站的首頁資訊。用 DFS 可能會在第一個網站就爬了1000個頁面，而其他99個網站都還沒看！

2. 分散請求壓力：BFS 會輪流訪問不同網站，就像排隊一樣公平。DFS 則會連續敲同一個伺服器的門，可能被當成攻擊！

3. 重要資訊在前幾層：大部分有價值的內容都在網站的前幾層（首頁、分類頁）。BFS 能快速覆蓋這些重點。

4. 更好的控制：你可以說「我只要爬3層深度」，BFS 會均勻地給你所有網站的前3層。DFS 則可能只給你一個網站的超深層內容。