Tree and Graph

在開始今天的主題之前，要先來淺談Tree跟Graph。什麼是Tree？

Tree

1. Tree 是一種特定的Graph，沒有Loop
2. Tree 只有唯一的Root

Graph

1. Graph是一種抽象資料類型
2. Graph是一個有限集合
3. 點跟點相連的線稱為「edges」，edges分為有方向性(Directed Graph)或無方向性(Undirected Graph)

有向圖(Directed Graph)

有向圖顧名思義是在圖形中表示某個邊的單邊通行，有時候會在邊上加上權重。實際應用於網頁連結等等。

無向圖(Undirected Graph)

無向圖跟有向圖差別在沒有方向，但也可以設定權重。

廣度優先搜尋(breadth-first search(BFS))

最初假設自己在某個頂點（稱為起點）。目的是從起點經由邊搜尋頂點，直到找到目標頂點。抵達頂點時，可以判定這個頂點是否為目標頂點，廣度優先搜尋在搜尋頂點時，優先搜尋離起點較近的頂點

頂點選項：「先進先出」(FIFO)，所以可以用「佇列」的資料結構

有可能是封閉迴圈（closed circuit)，也就是迴圈上起點和終點在同一個路徑的狀態，若非封閉迴圈形式，則稱為「樹」(tree)