圖算法

定義

在計算中，常將運算方程或實驗結果繪製成由若干有標尺的線條所組成的圖，稱為“算圖”或“諾模圖”。計算時根據已知條件，從有關線段上一點開始，連結相關線段上的點，連線與表示所求量線段的交點即為答案。

無向圖、有向圖和網路能運用很多常用的圖算法。這些算法包括：各種遍歷算法（這些遍歷類似於樹的遍歷），尋找最短路徑的算法，尋找網路中最低代價路徑的算法，回答一些簡單相關問題（例如，圖是否是連通的，圖中兩個頂點間的最短路徑是什麼，等等）的算法。

圖的遍歷是指從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作是圖的一種基本操作，圖的許多操作都建立在遍歷操作的基礎之上。

由於圖中節點之間的關係是任意的，所以圖的遍歷要比樹的遍歷複雜，主要表現在以下四個方面：

（1）在圖結構中，沒有一個明顯的首結點，圖中任意一個頂點都可作為第一個被訪問的結點，所以要提供首結點。

（2）在非連通圖中，從一個頂點出發，只能夠訪問它所在的連通分量上的所有頂點，因此，還需考慮如何選取下一個出發點，以訪問圖中其餘的連通分量。

（3）在圖結構中，可能有迴路存在，那么一個頂點被訪問之後，有可能沿迴路又回到該頂點，在訪問之前，需要判斷結點是否已經被訪問過。

（4）在圖結構中，一個頂點可以和其它多個頂點相連，當這樣的頂點訪問過後，存在如何選取下一個要訪問的頂點的問題。

因此，在遍歷圖時，為保證圖中各頂點在遍歷的過程中訪問且僅一次，需要為每個頂點設計一個訪問標記，設定一個數組，用於標示圖中每個頂點被訪問過，它的初始值全部為0，表示頂點均未被訪問過；某個頂點被訪問後，將相應訪問標誌數組中的值設為1，以表示該頂點已經被訪問過。

通常，圖的遍歷有兩種：
（1）深度優先遍歷搜尋；

對於有n個頂點的無向連通圖，至少有n-1條邊，而生成樹恰好有n-1條邊，所以生成樹是圖的極小連通子圖。如果無向連通圖是一個網，那么它的所有生成樹中必有一棵邊的權值總和最小的生成樹，稱這顆生成樹為最小生成樹。

1.從一個源點到其它各點的最短路徑，可使用迪傑斯特拉算法來求最短路徑。

2.每一對頂點之間的最短路徑，可使用弗洛伊德算法來求解。

用來解決傳輸水、油或其它液體等實際問題的方法。如果管道的分發點代表圖中頂點，連線這些分發點的管道作為圖的邊，並且其代價由圖中邊的代價決定，那么最小生成樹提供了一個最好的方法來布置一個可以連線所有分發點的管道模型。