12.廣度優(yōu)先算法：一種圖算法，解決最短（空間）路徑算法問題

1.建立圖問題模型

2.使用廣度優(yōu)先搜索：一級圓擴散到多級圓，使用隊列實現(xiàn)，F(xiàn)IFO（先進先出）

3.棧：LIFO，后進先出

4.圖映射：每個節(jié)點向外擴散一級到對應(yīng)的下一級連接的數(shù)組集合

5.有向圖：單向 ? ?無向圖：雙向

6.實現(xiàn)圖：

1.創(chuàng)建一個隊列deque

2.從隊列中彈出一個人

3.檢查這個人是否滿足要求 是 ?否

4.否，將這個人的鄰居加入隊列，返回第二步

5.隊列為空，說明沒有目標

? ? ? ? ? ? ? ?7.樹是圖的子集，因此樹都是圖

1. 狄克斯特拉算法（僅適用于有向無環(huán)圖）：找出最快（事件）路徑算法

   （1）找到最便宜的節(jié)點

   （2）找到這個節(jié)點開銷最少的鄰節(jié)點

   （3）重復(fù)找鄰節(jié)點，直到最終節(jié)點

   （4）計算最終路徑

   （5）實現(xiàn)：

   
   

2. 權(quán)重：每條邊的開銷，帶開銷數(shù)字的稱為加權(quán)圖，不帶開銷數(shù)字稱為非加權(quán)圖

   
   

3. 貝爾曼-福德算法：在狄克斯特拉算法不能計算負權(quán)邊的基礎(chǔ)上改進，可以計算圖的負權(quán)邊最快路徑（可以是其他變量）

#編寫散列表graph