-
圖算法
鎖定
圖算法指利用特製的線條算圖求得答案的一種簡便算法。無向圖、有向圖和網絡能運用很多常用的圖算法,這些算法包括:各種遍歷算法(這些遍歷類似於樹的遍歷),尋找最短路徑的算法,尋找網絡中最低代價路徑的算法,回答一些簡單相關問題(例如,圖是否是連通的,圖中兩個頂點間的最短路徑是什麼,等等)的算法。圖算法可應用到多種場合,例如:優化管道、路由表、快遞服務、通信網站等。
- 中文名
- 圖算法
- 外文名
- Graph algorithm
- 常用圖算法
- 圖的遍歷、最小生成樹、最短路徑
- 應用案例
- 優化管道、路有表、快遞服務等
- 應用基礎
- 無向圖、有向圖、網絡
- 基礎知識
- 圖的定義、術語及存儲結構
圖算法定義
在計算中,常將運算方程或實驗結果繪製成由若干有標尺的線條所組成的圖,稱為“算圖”或“諾模圖”。計算時根據已知條件,從有關線段上一點開始,連結相關線段上的點,連線與表示所求量線段的交點即為答案。
[1]
無向圖、有向圖和網絡能運用很多常用的圖算法。這些算法包括:各種遍歷算法(這些遍歷類似於樹的遍歷),尋找最短路徑的算法,尋找網絡中最低代價路徑的算法,回答一些簡單相關問題(例如,圖是否是連通的,圖中兩個頂點間的最短路徑是什麼,等等)的算法。
[2]
圖算法常用的圖算法
圖算法圖的遍歷
由於圖中節點之間的關係是任意的,所以圖的遍歷要比樹的遍歷複雜,主要表現在以下四個方面:
(1)在圖結構中,沒有一個明顯的首結點,圖中任意一個頂點都可作為第一個被訪問的結點,所以要提供首結點。
(2) 在非連通圖中,從一個頂點出發,只能夠訪問它所在的連通分量上的所有頂點,因此,還需考慮如何選取下一個出發點,以訪問圖中其餘的連通分量。
(3)在圖結構中,可能有迴路存在,那麼一個頂點被訪問之後,有可能沿迴路又回到該頂點,在訪問之前,需要判斷結點是否已經被訪問過。
因此,在遍歷圖時,為保證圖中各頂點在遍歷的過程中訪問且僅一次,需要為每個頂點設計一個訪問標記,設置一個數組,用於標示圖中每個頂點被訪問過,它的初始值全部為0,表示頂點均未被訪問過;某個頂點被訪問後,將相應訪問標誌數組中的值設為1,以表示該頂點已經被訪問過。
通常,圖的遍歷有兩種:
(1)深度優先遍歷搜索;
圖算法最小生成樹
對於有n個頂點的無向連通圖,至少有n-1條邊,而生成樹恰好有n-1條邊,所以生成樹是圖的極小連通子圖。如果無向連通圖是一個網,那麼它的所有生成樹中必有一棵邊的權值總和最小的生成樹,稱這顆生成樹為最小生成樹。
圖算法最短路徑
1.從一個源點到其它各點的最短路徑,可使用迪傑斯特拉算法來求最短路徑。
圖算法應用
圖算法優化管道
用來解決傳輸水、油或其它液體等實際問題的方法。如果管道的分發點代表圖中頂點,連接這些分發點的管道作為圖的邊,並且其代價由圖中邊的代價決定,那麼最小生成樹提供了一個最好的方法來佈置一個可以連接所有分發點的管道模型。
[4]
圖算法路由表
在互聯網中,路由器利用路由表直接尋址轉發數據。路由器存在的目的是將數據傳送到離目的更近的地方。在某些路由過程中,路由器會週期性的計算它到另一個路由器的最短路徑,這樣它們就知道接下來將數據發送到哪個目的地址是最佳方案。
[4]
圖算法快遞服務
圖算法通信網絡
圖算法航路選擇
這是一個對航空公司和空中交通管制機構很重要的優化問題。通常飛機不能從一個地方直接飛到另一個地方。所以,他們在空中建立航線或高速航道,這些航道同時考慮了風速、機票的費用和空中交通管制的限制。那麼,考慮了所有以上的這些因素後,兩地之間的最佳航線就是圖中權值最小的路徑。
[4]
圖算法閉合運輸系統
圖算法有線電路板
電子製造業中的一個優化問題。通常,使電路板上一些組件的引腳相互之間連接起來是必要的。如果每個引腳代表圖中的一個頂點,其連線作為邊,且邊的權由連線的數量決定。那麼最小生成樹能提供一種連接引腳的最優方法。
[4]