圖形搜尋

授課老師

林子婷

適合學習對象

高中生

課程目標

上完課程後，學生應具備的知識與能力：

• 能以文字表示圖形資訊

• 能以相鄰矩陣表示圖形資訊

• 能以相鄰串列表示圖形資訊

• 會使用深度優先搜尋法進行圖形搜尋

• 會使用廣度優先搜尋法進行圖形搜尋

• 能撰寫出搜尋法的文字式程式

先備知識

• 會使用矩陣(matrix)、遞迴(Recursive)等C++語法及架構撰寫程式

• 具備堆疊(stack)、佇列(queue)等概念

• 瞭解樹(tree)的基本架構及概念

核心素養/運算思維

• 科 S-U-A2 運用科技工具與策略進行系統思考與分析探索，並有效解決問題

學習重點

*學習表現*

• 運 t-V-2 能使用程式設計實現運算思維的解題方法

• 運 t-V-3 能應用運算思維評估解題方法的優劣

• 運 r-V-4 能發展演算法以解決運算問題

*學習內容*

• 資 A-V-1 重要資料結構的概念與應用

課程單元

*教學影片播放清單: 連結

1.  什麼是圖形搜尋？

   • 教學影片連結

   • 課後練習解答

   • 課後練習解答講解影片

2. 深度優先搜尋

   • 教學影片連結

3. C++深度優先搜尋實作－走訪路徑

   • 教學影片連結

   • 深度優先搜尋實作練習－架構連結

   • 深度優先搜尋實作練習－解答篇

   • 深度優先搜尋實作練習－搜尋特定目標

4. 廣度優先搜尋

   • 教學影片連結

5. C++廣度優先搜尋實作－走訪路徑

   • 教學影片連結

   • 廣度優先搜尋實作練習－架構連結

   • 廣度優先搜尋實作練習－解答篇

   • 廣度優先搜尋實作練習－搜尋特定目標

實作題測試資料

• 優先搜尋實作測試資料

參考連結

• 網站

1. 【演算法】圖形搜尋法 Graph Searching Methods 

2. 縱向優先搜尋 (depth-first search)

3. 深度優先搜尋法 (Depth-first Search)

4. 演算法筆記-Graph

• 書籍

演算法圖鑑 作者：石田保輝, 宮崎修一 / 譯者：陳彩華