加權圖和應用

如果每條邊都分配了權重，那麼圖就是加權圖。加權圖有許多實際應用。

上圖假設該圖代表城市之間的航班​​數量。您可以應用 BFS 來尋找兩個城市之間的最少航班數量。假設邊代表城市之間的行駛距離，如下圖所示。如何找到連接所有城市的最小總距離？如何找到兩個城市之間的最短路徑？本章將解答這些問題。前者稱為最小生成樹（MST）問題，後者稱為最短路徑問題。

上一章介紹了圖的概念。您學習如何使用邊數組、邊列表、鄰接矩陣和鄰接列表來表示邊，以及如何使用Graph 介面、AbstractGraph 類別和Abstract 類別和

UnweightedGraph 類。前面的章節也介紹了圖遍歷的兩種重要技術：深度優先搜尋和廣度優先搜索，並應用遍歷來解決實際問題。下面的文章將介紹加權圖。您將學習在 post 中尋找最小生成樹的演算法以及在 post 中尋找最短路徑的演算法。

以上是加權圖和應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！