4–1 何謂圖形 Graph
計算機科學或是離散數學中提到的“圖形”，指的是由節點(nodes, 也稱vertices)和連接節點的邊(edges)所組成的。
如下圖：
生活中有很多事物可以藉由這種圖形來表達，例如人際網絡，捷運路線圖，計算機網路等。
除了上圖這種最基本的圖形之外，圖形還可以有以下幾種變化：
- 加權圖形 Weighted Graph — 在邊上有數字表示兩點之間的連接的程度，而這裡指的“連接程度”會因為圖形實際的內容而異。例如人際網路圖的權重可能是兩個人在一個月內見面的次數，路線圖的權重可能會是兩地之間的距離。而權重也有可能設在節點上。
- 有向圖 Directed Graph — 連接兩點的線可以是有方向性的，反之像上圖那種沒有方向性的稱為”無向圖“。有向圖可以用來表示公車路線圖中表示某兩站只能單邊通行，該路線的公車在行駛某個方向時不會停靠某站之類的。有向圖當然也可以加上權重，如果兩點間是雙向的，這兩條方向相反的線上可以被賦予不同的權重 (非對稱權重)。例如兩地之間的路線是一個山坡，若權重數字表示前進到另一點的時間，上坡方向的權重可能就會比下坡方向來得大。
圖形可以用來解決很多問題，例如兩地之間的最短路徑，花費最便宜的路徑，計算機網路中通訊時間最短的路徑等。
4–2 廣度優先搜尋 Breadth-First Search
圖形搜尋演算法的目的是：從一個指定節點開始 (起點)，由邊搜尋節點，直到找到指定的節點 (目標節點)。抵達節點時要判定此節點是否為目標節點。
而廣度優先搜尋在搜尋時，會以”距離起點較近“的節點為優先，進行廣泛的搜尋。
以上圖為例，目標是要從1開始找到10，但我們事先不會知道10在哪裡。
首先，從1開始進行廣度優先搜尋，1可以抵達的點有8, 5, 2。但這三點之中，要從哪一個開始繼續下一步呢？這裡使用“First In First Out”的原則，從”最早被加入資料結構“的節點開始，所以可以使用之前提過的佇列(1–5)資料結構 。在這個階段，8, 5, 2同時被加入資料中，這種時候可以隨機選擇，假設我們選擇並移動到最左邊的8。
移動到8之後，節點6, 4, 3也被加入可以移動的選項，而在5, 2, 6, 4, 3 中，最早被加入資料結構的是5和2, 我們在兩者中隨機移動到5。
5之後沒有路可以走，所以我們在2, 6, 4, 3中繼續搜尋，按照先進先出的原則，移動到2。
這個時候，選項變成有6, 4, 3, 9，重複執行上述的搜尋，直到找到目標10。
在這個例子中，幾乎快要搜尋完整個圖形才找到我們的目標。但當目標離起點很近的時候，廣度優先搜尋可以很快的找到目標。
4–3 深度優先搜尋 Depth-First Search
和廣度優先的概念相反，深度優先會一路往某個方向深入搜尋，直到確定這條路無法抵達目標，才會折返搜尋下一條路線。
另一點和廣度優先不同的是，選擇節點的原則是”Last In First Out”，因此可以用堆疊(1–4)來管理數據。針對同時被加入的節點們，一樣可以隨機選擇。
以4–2的圖形作為例子，由1開始，可以抵達的點有8, 5, 2。
8, 5, 2是同時被加入資料中的，這時候可以隨機選擇，假設我們選擇並移動到最左邊的8。
8可以移動到的節點有6, 4, 3，所以現在候選的節點有5, 2, 6, 4, 3，我們在最晚被加入的6, 4, 3中隨機選擇6。
此時10, 7又被加入選項，按照後進先出原則，如果我們在10, 7中隨機選擇到10，搜尋便完成了。
