在開始各類圖算法之前，先將圖的結構進行分類。

圖的表示，在實際實現過程中。有下面幾種主要的方式能夠來表示圖。
1） 鄰接矩陣：對于較小或者中等規模的圖的構造較為適用。因為須要V*V大小的空間。
2） 邊的數組：使用一個簡單的自己定義edge類，還有兩個變量，分別代表邊的兩個端點編號，實現簡單，可是在求每一個點的鄰接點的時候實現較為困難。
3） 鄰接表數組：較為經常使用，使用一個以頂點為索引的數組。數組每一個元素都是和該頂點相鄰的頂點列表。這樣的數組占空間相對于鄰接矩陣少了非常多。而且能非常好的找到某個給定點的全部鄰接點。

依照圖中邊的方向將圖分成有向圖和無向圖：
1）無向圖：圖中的邊沒有方向。

2）有向圖：圖中的邊有方向。
對于有向圖和無向圖的詳細實現表示能夠使用前面介紹的三種方法。兩種圖在表示的時候大部分的實現代碼都是一致的。

普通無向圖的鄰接數組表示方法的詳細實現代碼：

public class Graph {private int V; //圖中的頂點數目private int E; //圖中的邊數目private List<Integer>[] adj; //鄰接數組private int[][] a; //鄰接矩陣public CreatGraph(int V) { this.E = 0;this.V = V;adj = new ArrayList[V];a=new int[V][V];for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();}//因為無向圖中的邊是沒有方向的，所以加入邊的時候須要在邊的兩個頂點相應的鄰接列表中都加入頂點信息。

public void addEdge(int v1, int v2) { a[v1][v2]=1; a[v2][v1]=1; adj[v1].add(v2); adj[v2].add(v1); E++; } public int V() { return V; } public int E() { return E; } //鄰接數組返回給定點的全部鄰接點 public List<Integer> adj(int i) { return adj[i]; } //鄰接矩陣返回給定點的全部鄰接點 public List<Integer> adj1(int i){ List<Integer> list=new ArrayList<>(); int[] adj1=new int[V]; adj1=a[i]; for(int v:adg1) if(v!+0)list.add(v); return list; } }

無權有向圖的詳細實現代碼：

public class DirectedGraph {private int V; //圖中的頂點數目private int E; //圖中的邊數目private List<Integer>[] adj; //鄰接數組private int[][] a; //鄰接矩陣public DirectedGraph(int V) {this.E = 0;this.V = V;adj = new ArrayList[V];a=new int[V][V];for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();}//因為無向圖中的邊是有方向的，所以加入邊的時候須要僅僅須要在起始點的鄰接列表中加入頂點信息。

public void addEdge(int v1, int v2) { a[v1][v2]=1; adj[v1].add(v2); E++; } public int V() { return V; } public int E() { return E; } //鄰接數組返回給定點的全部鄰接點 public List<Integer> adj(int i) { return adj[i]; } //鄰接矩陣返回給定點的全部鄰接點 public List<Integer> adj1(int i){ List<Integer> list=new ArrayList<>(); int[] adj1=new int[V]; adj1=a[i]; for(int v:adg1) if(v!+0)list.add(v); return list; } }

一 圖的遍歷算法：

介紹兩種比較基礎的圖遍歷算法，廣度優先搜索和深度優先搜索。

1）深度優先搜索：這是一種典型的遞歸算法用來搜索圖（遍歷全部的頂點）；
思想：從圖的某個頂點i開始，將頂點i標記為已訪問頂點，并將訪問頂點i的鄰接列表中沒有被標記的頂點j，將頂點j標記為已訪問，并在訪問頂點j的鄰接列表中未被標記的頂點k依次深度遍歷下去，直到某個點的全部鄰接列表中的點都被標記為已訪問后。返回上層。反復以上過程直到圖中的全部頂點都被標記為已訪問。

深度優先遍歷和樹的先序訪問非常相似，盡可能深的去訪問節點。深度優先遍歷的大致過程（遞歸版本號）：
a）在訪問一個節點的時候，將其設置為已訪問。
b）遞歸的訪問被標記頂點的鄰接列表中沒有被標記的全部頂點
（非遞歸版本號）:
圖的非遞歸遍歷我們借助棧來實現。

a）假設棧為空，則退出程序，否則，訪問棧頂節點，但不彈出棧點節點。
b）假設棧頂節點的全部直接鄰接點都已訪問過，則彈出棧頂節點。否則，將該棧頂節點的未訪問的當中一個鄰接點壓入棧。同一時候，標記該鄰接點為已訪問，繼續步驟a。
該算法訪問頂點的順序是和圖的表示有關的，而不僅僅是和圖的結構或者是算法有關。

深度優先探索是個簡單的遞歸算法(當然借助棧也能夠實現非遞歸的版本號)，可是卻能有效的處理非常多和圖有關的任務，比方：
a) 連通性：ex:給定的兩個頂點是否聯通 or 這個圖有幾個聯通子圖。
b) 單點路徑：給定一幅圖和一個固定的起點，尋找從s到達給定點的路徑是否存在，若存在。找出這條路徑。

尋找路徑：
為了實現這個功能，須要在上面實現的深度優先搜索中中添加實例變量edgeTo[]，它相當于繩索的功能。這個數組能夠找到從每一個與起始點聯通的頂點回到起始點的路徑（詳細實現的思路非常巧妙： 從邊v-w第一次訪問w的時候，將edgeTo[w]的值跟新為v來記住這條道路，換句話說，v-w是從s到w的路徑上最后一條已知的邊，這樣搜索結果就是一條以起始點為根結點的樹，也就是edgeTo[]是個有父鏈接表示的樹。

）

深度優先搜索的遞歸實現版本號和非遞歸版本號（遞歸是接住了遞歸中的隱藏棧來實現的。非遞歸，借助棧實現）

import java.util.ArrayList; import java.util.Collections; import java.util.List;public class DepthFirstSearch {//用來記錄頂點的標記狀態 true表示為已訪問。false表示為未被訪問。private boolean[] marked; private int count; //用來記錄頂點索引所相應的父結點。假設遍歷是從s到達的t那么edgeTo[s所對的所用]=t;private int[] edgeTo; //起始點private int s; private Deque<Integer> dq=new Deque<>();public DepthFirstSearch(Graph G, int s) {marked = new boolean[G.V()];edgeTo = new int[G.V()];this.s = s; dq.push(s);dfs(G, s);}//遞歸形式實現public void dfs(Graph G, int s) { marked[s] = true;count++;for (int temp : G.adj(s))if (!marked[temp]) {edgeTo[temp] = s;dfs(G, temp);}}//非遞歸形式實現private void dfs(Graph G){while(!dp.isEmpty()){s=dp.peek();needPop=true;marked[s] = true;for (int temp : G.adj(s))if (!marked[temp]) {dp.push(temp);edgeTo[temp] = s;needPop=false;break;}}if(needPop)dp.pop();}public boolean hasPathTo(int v) {return marked[v];}public List<Integer> pathTo(int v) {if (hasPathTo(v))return null;List<Integer> list = new ArrayList<>();v = edgeTo[v];while (v != s) {list.add(v);v = edgeTo[v];}list.add(s);Collections.reverse(list);return list;}public int count() {return count;}public static void main(String[] args){int V = 0,E = 0;Graph G=new Graph(V,E);int s=0;DepthFirstSearch dfs=new DepthFirstSearch(G,s);for(int v=0;v<G.V();v++){if(dfs.hasPathTo(v))for(int x:dfs.pathTo(v))if(x==s)System.out.print(x);elseSystem.out.print("-"+x);System.out.println();}} }

已經使用DFS攻克了一些問題，DFS事實上還能夠解決非常多在無向圖中的基礎性問題。譬如：
1）計算圖中的連通分支的數量；

public class ConnectComponent {private boolean[] marked;private int[] id; //標記結點所在的連通分支編號private int count; //計算連通分支的個數public ConnectComponent(Graph G) {marked = new boolean[G.V()];id = new int[G.V()];for (int s = 0; s < G.V(); s++) {if (!marked[s]) {dfs(G, s);count++;}}}public void dfs(Graph G, int s) {marked[s] = true;id[s] = count;for (int temp : G.adj(s))if (!marked[temp]) {dfs(G, temp);}}//推斷點v和w是否在一個連通分支中public boolean connected(int v, int w) {if (id[v] == id[w])return true;elsereturn false;}public int id(int v) {return id[v];}public int count() {return count;} }

2）環檢測：檢測圖中是否有環。

public class CycleDetect {private boolean[] marked;private boolean flag;public CycleDetect(Graph G) {marked = new boolean[G.V()];for (int s = 0; s < G.V(); s++) {if(!marked[s])dfs(G, s, s);} }public void dfs(Graph G, int s, int initial) {marked[s] = true;for (int temp : G.adj(s))if (!marked[temp]) {dfs(G, temp, initial);} else {if (temp == initial) {flag = true;return;}}}public boolean hasCycle(){return flag;}}

3）二分圖推斷（雙色問題）：是否能用兩種顏色給這個二分圖進行著色，也就是說這個圖是不是二分圖。

public class IsBiagraph {private boolean[] marked;private boolean[] color;private boolean flag=true;public IsBiagraph(Graph G) {marked = new boolean[G.V()];color=new boolean[G.V()];for (int s = 0; s < G.V(); s++) {if(!marked[s])dfs(G, s);}}public void dfs(Graph G, int s) {marked[s] = true;for (int temp : G.adj(s))if (!marked[temp]) {color[temp]=!color[s];dfs(G, temp);} else{if(color[temp]==color[s])flag=false;} }public boolean isBiagraph (){return flag;} }

2）廣度優先搜索：
前面說過。深度優先搜索得到的路徑不僅取決于圖的結構，還取決于圖的表示以及遞歸調用的性質，可是假設要求最短的路徑（給定圖G和起始點s尋找給定點v和s間是否存在路徑，假設存在。找出最短的路徑）。那么使用前面的DFS算法并不能解決該問題，所以出現了廣度優先搜索BFS來實現這個目的，廣度優先搜索也是其它算法的基礎。
在程序中，搜索一幅圖的時候會遇到有非常多條邊都須要被遍歷的情況，我們會選擇當中一條并將其它邊留到以后再繼續搜索。在DFS中使用棧結構，使用LIFO的規則來描寫敘述。從有待搜索的通道中選取最晚遇到的那個通道，然而在BFS算法中。我們希望依照與起點的距離來遍歷全部的頂點，使用FIFO（隊列）來進行搜索，也就是搜索最先遇到的那個通道。

BFS:使用一個隊列來保存全部已經被標記過的可是其鄰接點還未被檢查過的頂點。現將頂點加入隊列中，然后反復下面的操作。直至隊列為空：
1）取隊列中的下一個頂點v并標記它
2）將與v相鄰的全部的未被標記的頂點加入隊列中。

廣度優先搜索相似于樹的按層遍歷

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.Deque; import java.util.List;public class BreadFirstSearch {private boolean[] marked;private int[] edgeTo;private int s;public BreadFirstSearch(Graph G, int s) {marked = new boolean[G.V()];edgeTo = new int[G.V()];this.s = s;bfs(G, s);}public void bfs(Graph G, int s) {Deque<Integer> deque = new ArrayDeque<>();marked[s] = true;deque.addFirst(s);while (!deque.isEmpty()) {s = deque.removeLast();for (int temp : G.adj(s))if (!marked[temp]) {deque.push(temp);marked[temp] = true;edgeTo[temp] = s;}}}public boolean hasPathTo(int v) {return marked[v];}public List<Integer> pathTo(int v) {if (hasPathTo(v))return null;List<Integer> list = new ArrayList<>();v = edgeTo[v];while (v != s) {list.add(v);v = edgeTo[v];}list.add(s);Collections.reverse(list);return list;}}

DFS和BFS是兩種基礎的通用的圖搜索算法。在搜索中我們都運用下面方法：
將起始點加入入某個數據結構中，然后反復下面步驟直至數據結構中的全部數據都被清空。
1） 取數據結構的下個數據v而且標記它。
2） 將v全部的相鄰的未被標記的頂點加入到數據結構中。

這兩種算法每次都擴展一個節點的全部子節點。而不同的是，深度搜索下一次擴展的是本次擴展出來的子節點中的一個，而廣度搜索擴展的則是本次擴展的節點的兄弟節點
使用范圍：DFS能夠迅速的找到一個解，然后利用這個解進行剪枝，而BFS可找到最優解。
將上述的圖像數據類型改成有向圖就能夠實現有向圖中的遍歷問題。
在有向圖中單點的聯通問題（即給定的兩點是否聯通）變成了可達問題（即對于給定的兩個是否存在一條有向路）在有向圖中，使用全然同樣的代碼。在就能夠在有向圖中就能夠解決可達問題。

public class DirecedtDFS {public boolean[] marked;public DirecedtDFS(DiGraph G, int s) {marked = new boolean[G.V()];dfs(G, s);}public DirecedtDFS(DiGraph G, Set<Integer> set) {marked = new boolean[G.V()];for (int s : set)if (!marked[s])dfs(G, s);}private void dfs(DiGraph G, int s) {marked[s] = true;for (int temp : G.adj[s])if (!marked[temp])dfs(G, temp);}public boolean marked(int i) {return marked[i];} }

然而在有向圖中的環檢測就和無向圖中不大一樣，須要保存某條道路上的全部信息。來推斷是否形成有向環。
在運行dfs(G,s)的時候查找的總是一條由起點到達s的有向路徑。要保存這條路徑，程序實現的時候維護了一個由頂點索引的boolean類型數組onStack用來標記遞歸調用棧上的全部頂點（在dfs調用的時候，將onStack[s]設置成true,結束的時候（就是這條有向路結束了）再將其設置為false）當它在找到一條邊v→w時候，w已經在棧中（這里的是表示這個點已經在這條路上出現過了，也就是在onStack中已經標記過了）它就找到可一個有向環，環上的頂點和無向圖一樣能夠通過edgeTo數組獲得。這里在檢測遇到的點w是否在棧中，不像無向圖那樣檢查是否在marked中標記過，是因為，在有向圖中的環必須是一條首尾結點一樣的有向路。環上的全部有向邊的方向必須一致。

public class DirectedCycle {private boolean marked[];private int edgeTo[];private boolean onStack[];List<Integer> list;private boolean flag;public DirectedCycle(DiGraph G) {//標記整個圖上的遍歷過的結點marked = new boolean[G.V()];//標記某條有向路上遇到的全部節點onStack = new boolean[G.V()]; edgeTo = new int[G.V()];for (int v = 0; v < G.V(); v++) {dfs(G, v);}}private void dfs(DiGraph G, int s) {onStack[s] = true;marked[s] = true;for (int w : G.adj[s]) if (hasCycle())return;else if (!marked[w]) {dfs(G, w);edgeTo[w] = s;} else if (onStack[w]) {list = new ArrayList<>();for (int v = s; v != w; v = edgeTo[v])list.add(v);list.add(w);list.add(s);}onStack[s]=false;}public boolean hasCycle() {return list.isEmpty();}public List<Integer> cycle() {return list;} }

3）拓撲排序：
拓撲排序：給定一幅有向圖，給全部的結點排序，排序后使得有向邊均從排在前面的結點元素指向排在后面的結點元素（或者說明這個有向圖不能進行拓撲排序）。

在對一個有向圖進行拓撲排序的時候，必須保證它是無環的有向圖，因為有環的圖不能做到拓撲有序。
事實上對于標準的深度優先搜索算法加入一行代碼就能實現這個問題。在使用深度優先搜索的時候，正好僅僅會訪問每一個結點一次，假設將dfs()訪問的結點存儲在一個數據結構中，然后遍歷這個結構就能夠訪問圖中全部結點。遍歷的順序取決于這個數據結構的性質以及是在遞歸前還是遞歸后保存
1） 前序：在遞歸前將頂點放入隊列中
2） 后序：在遞歸調用之后將頂點放入隊列中
3） 逆后序：在遞歸調用之后將頂點壓入棧中。

一幅有序無環圖的拓撲排序就是全部頂點的逆后序排列。

public class DFSOrder {private boolean[] marked;private List<Integer> pre; //前序private List<Integer> post; //后序private Deque<Integer> reseverpost; //逆后序public DFSOrder(DiGraph G){marked=new boolean[G.V()];pre=new ArrayList<>(G.V());post=new ArrayList<>(G.V());reseverpost=new ArrayDeque<>(G.V());for(int v=0;v<G.V();v++)dfs(G,v); }public DFSOrder(EdgeWeightDigraph G){marked=new boolean[G.V()];pre=new ArrayList<>(G.V());post=new ArrayList<>(G.V());reseverpost=new ArrayDeque<>(G.V());for(int v=0;v<G.V();v++)dfs(G,v); }private void dfs(DiGraph G, int v) {pre.add(v);marked[v]=true;for(int w:G.adj[v])if(!marked[w])dfs(G,w);post.add(v);reseverpost.addLast(v);} public List<Integer> pre(){return pre;}public List<Integer> post(){return post;}public Deque<Integer> reseverpost(){return reseverpost;} }

拓撲排序實現代碼：

public class Topological {private Deque<Integer> oder=new ArrayDeque<>(); public Topological(DiGraph G){DirectedCycle cycle=new DirectedCycle(G);if(!cycle.hasCycle()){DFSOrder dfsorde=new DFSOrder(G);oder=dfsorde.reseverpost();} } public boolean isDAG(){return oder!=null; } public Deque<Integer> order(){return oder; } }

使用深度優先搜索進行拓撲排序，事實上是使用了兩遍深度優先搜索，一遍是查看有向圖中是否存在有向環第二遍就是產生頂點的逆后序。因為兩次都訪問了全部的頂點和邊，所以這個算法須要的時間是和V+E成正比的。

深度優先搜索須要先預處理，而它使用的時間和空間與V+E成正比。且在常數時間內處理關于圖的連通性。Union-find也能夠進行圖搜索，可是實際上。union-find事實上更加快。因為不須要構造并表示一幅圖，而且union-find算法是一種動態算法，可是深度優先算法須要對圖進行預處理。

我們在完畢僅僅須要推斷連通性或是須要完畢大量的連通性查詢和插入操作混合等相似的任務時。更加傾向于使用union-find算法，而深度優先算法則跟適合實現圖的抽象數據類型。
補充說明：Union-find算法(解決動態連通性問題)：
問題描寫敘述：給出一列整數對。每一個整數對（p,q）能夠被覺得是相連的，我們假定相連是一種等價關系（這樣的相連的屬性滿足自反性，對稱性以及傳遞性，從圖的角度來看，這個整數對能夠看作無向邊的兩個端點）。這樣的等價關系將輸入的數據對劃分為多個等價類（從圖的角度來看，是將他們劃分為多個連通分量）我們須要設計一種數據結構。來保存已經輸入的數據對象（即已知的數據對）的全部信息，并用這些信息來推斷，新的數據對是否是相連的（也就是新加入進的邊的兩個端點是否在同一個連通分支內），將這個問題通俗的稱為動態連通性問題。這和我們前面所講的使用DFS來推斷圖的連通性能夠達到一樣的目的，可是這個是在動態生成的過程中推斷圖的連通性。而DFS須要預處理整個圖，不能在動態的過程中來推斷。
union-find 算法中API：
1）void union(int v,int w) 在p和q之間加入一條連接
2）int find(int v) p所在的分量的標識
3）boolean connected(int v,int w)假設p和q在同一個分量中。那么返回true
4）int count() 返回連通分量的數目；
在詳細實現過程中，選擇一個以頂點為索引的數組，來記錄相應頂點所在的聯通分支的標識（將使用連通分量中某個頂點作為該分支的標識），在union中，假設p和q不在一個連通分量中，那么須要更具不同的算法改變其id數組中的值，假設在同一分量中，忽略不計就可以。

public class UF {private int[] id;private int count;public UF(int N) {id = new int[N];count = N;for (int i = 0; i < N; i++)id[i] = i;}public int count() {return count;}public boolean connect(int v, int w) {return quick_find(w) == quick_find(v);} }

這里將介紹三種find-union的實現方法（每種方法僅僅是find和union實現不太同樣），可是他們都是依據以頂點為索引的id數組來確定在不在同一連通分量中：
1）quick-find方法：
在這樣的方法中，同一個連通分量中的id值都是同樣的。

在find實現的時候，直接返回id中的值就可以。

在union實現的時候，先推斷給定的數據對是否在同一個連通分量中。假設是就直接忽略。否則，合并p和q所在的連通分量（就是將p所在的連通分量的標識id全部替換成q所在的連通分量標識id（反之亦可）），為此，我們須要遍歷整個數組；

public int quick_find(int w) {return id[w];}public void union(int v,int w) {//假設點v，w在同一個連通分量中，那么不須要採取不論什么措施if(connect(v,w)) return;//否則將v所在的連通分量的標記號全部改為w所在的連通分量的標記號碼int label_v=id[v];int label_w=id[w];for(int i=0;i<id.length;i++){if(id[i]==label_v)count--;}}

2）quick-union方法：
由上述可知。我們對于每對輸入都須要遍歷整個數組。因此quick-find無法處理大型數據，假設使用quick-find方法而且最后僅僅得到一個連通分支，那么至少須要調用N-1次union方法，每次union方法都須要至少N+3次操作，那么整個算法的性能就是平法級別的。而quick-union方法提高了union的效率。同樣也是基于同樣的數據結構-由頂點索引的id數組，可是該方法中的id數組的意義有所不同，這里的id[]中的元素都是同一個分量中其它頂點的編號。也有可能是自己，我們將這樣的聯系稱為鏈接。在find方法中。我們從給定的頂點開始。由它的鏈接得到另外一個頂點，再由這個頂點的鏈接得到新的頂點，如此繼續尾隨頂點的連接到達新的頂點，直到鏈接指向自己（這樣的鏈接所相應的頂點被稱為跟結點），和quick-find不同，quick-union僅僅有兩個頂點開始這一過程而且到達同樣的跟結點，才干說它們是同一個分支中的。所以在詳細的union實現中。我們須要依照上述過程找尋給定的兩個頂點的跟結點。假設跟結點同樣（說明這兩個頂點在同一個分量中）。否則，將當中一個根結點中的鏈接連接到另外一個跟結點上（也就是為當中一個跟結點的鏈接又一次定義為另外一個跟結點）這樣的實現find-union方式被稱為quick-union方法。

public int find(int v){while(v!=id[v]) v=id[v];return v;}public void quick_union(int v,int w){int lable_v=find(v);int lable_w=find(w);if(lable_v==lable_w) return;elseid[lable_v]=lable_w;count--;}

3）加權的quick-union:
可是在前面講的quick-union方法中，可能會出現依據不同的輸入可能出現最壞的情況。就是樹偏向一邊，也就是實現仍然須要平方級別的的消耗，在上述實現思想中，再做個輕微的改進就能極大的提高算法的效率，就是每次合并兩個分量的時候，不是隨意的合并。而是將較小的分量的跟結點的鏈接改為較大跟結點。這樣就能夠在以某種程度上達到平衡性，這里須要維護一個size數組。使得跟結點相應索引的元素的值為這個分量的大小（即分量中元素的個數）每次在進行合并須要改變id值得時候。比較兩個分量的跟結點的所在的分量的大小，總是將小的分量的鏈接改為大的分量的跟結點，而且跟新新的合成分量的跟結點的大小。

public void quick_weight_union(int v, int w) {int lable_v = find(v);int lable_w = find(w);if (lable_v == lable_w)return;if (size[v] > size[w])id[lable_w] = lable_v;elseid[lable_v] = lable_w;count--;}

4）使用路徑壓縮的加權quick-union方法：
在這樣的方法中，使得每一個節點都直接連接在其跟結點上，可是我們又不想像quick-find那樣遍歷整個數組，因此，在檢查頂點的同一時候將他們直接連接在跟結點上。要想實現路徑壓縮，僅僅須要為find方法加上一個循環，將在路上遇到的全部節點都連接到跟結點上。

二.最小生成樹：

在下面的討論中做出例如以下約定：
1） 僅僅考慮連通圖；
2） 邊的權重能夠是不論什么數；
3） 全部邊的權重都各不同樣(假設存在權值同樣的邊。最小生成樹不唯一)；
切分定理（解決最小生成樹的全部算法的基礎）：
將加權圖中的全部頂點分成兩個集合（兩個非空且不重合的集合）。檢查橫跨兩個集合的全部邊（這樣的邊被稱為橫切邊:一條連接兩個不屬于同一集合頂點的邊），并識別那條邊是否應該屬于圖的最小生成樹。

切分定理：在一幅加權圖中，給定隨意的劃分，它的橫切邊中權值最小者必定屬于最小生成樹。（證明：使用反證法，假設e為權值最小的橫切邊，T為圖的最小生成樹。假設T中不包括e,那么必定包括一條橫切邊f，將e邊加入最小生成樹中。形成了一個環，包括e, f邊，那么將f從環中刪去。生成一個新的生成樹T’顯然。新的生成樹比原來的最小生成樹更小，這與已知矛盾）
從切分定理可知。（在假設前提下，全部邊的權值都不同，那么最小生成樹是唯一的）對于每一種切分，權值最小的橫切邊必定屬于最小生成樹。

可是，權值最小的橫切邊并非全部橫切邊中唯一屬于圖的最小生成樹的邊，實際中。一次切分產生的橫切邊可能有多條屬于最小生成樹。
全部求解最小生成樹的算法都是使用的貪心策略（依據切分定理，每次選擇一種劃分。使得全部的橫切邊都沒有被標記。那么選擇權值最小的橫切邊，直至選擇了V-1條邊為止。僅僅只是對于不同的算法所使用的切分方法和推斷權值最小的橫切邊的方式有所不同。）
1）Prim算法：
思想：最開始樹中僅僅有一個頂點，每次為生長中的樹加入一個邊，直至加入了V-1條邊為止，每次加入的邊都是樹中的頂點和非樹中的頂點所劃分的兩個集合的橫切邊中最小的邊。

在詳細實現中使用一些簡單的數據結構來實現樹中點的標記（使用boolean類型的頂點索引數組來標記頂點是否在樹中），待選擇橫切邊（使用優先隊列來處理帶選擇的橫切邊，依據橫切邊的權重），生成樹中的邊（頂點索引的Edge對象數組來保存最小生成樹中的邊）。
我們使用一個方法來為樹加入頂點，將這個頂點標記為已訪問，而且將與它關聯的全部未失效的（連接新加入的節點和其它已經在樹中的頂點的全部邊失效）邊加入優先隊列中。然后取出優先隊列中權值最小的邊。而且檢查這個邊是否有效。假設有效，將這個邊的不在樹中的點標記為已訪問，并將這個邊加入最小生成樹的邊集合中，然后從優先隊列中刪除這個邊。調用新的頂點來更新橫切邊集合。
prim算法的延時實現代碼：

class Edge {int v;int w;double weight;public int other(int v) {if (v == this.v)return w;elsereturn v;}public int either() {return v;} }class EdgeWeightGraph {int V;public List<Edge>[] adj;public EdgeWeightGraph(int v) {for (int i = 0; i < v; i++) {adj[i] = new ArrayList<>();}}public int V() {return V;} }public class LazyPrimMST {private boolean[] marked; //標記最小生成樹的頂點private List<Edge> mst; //標記最小生成樹的邊private MinPQ<Edge> pq; //橫切邊（包括了失效的邊）public LazyPrimMST(EdgeWeightGraph G) {marked = new boolean[G.V()];mst = new ArrayList<>(G.V());pq = new MinPQ<Edge>();visit(G, 0);while (。pq.isEmpty()) {Edge temp = pq.delMin();int v = temp.either(), w = temp.other(v);if (marked[v] && marked[w])continue;mst.add(temp);if (!marked[v])visit(G, v);else if (!marked[w])visit(G, w);}}}private void visit(EdgeWeightGraph G, int i) {marked[i] = true;for (Edge temp : G.adj[i])if (!marked[temp.other(i)]) {pq.insert(temp);}} }

優化思想：改進Prim的延時實現，能夠嘗試在優先隊列中刪除失效的邊。這樣優先隊列就能夠僅僅包括真正的橫切邊。關鍵的優化思想在于：須要在意的僅僅是連接樹頂點和非樹頂點中權重最小的邊。也就是說，當我們將V加入到生成樹頂點集合中去后，對于每一個非樹頂點w不用保存w到樹的每條邊，僅僅須要保存權重最小的那個邊。也就是說，在優先隊列中，僅僅須要保存每一個非樹頂點的一條邊：將它和樹中頂點連接起來權重最小的那個邊。其它權重較大的邊遲早會失效。
即使實現的Prim算法：使用兩個頂點索引數組edgeTo[] 和distTo[]來替換延時實現中的marked和mst數據結構。
EdgeTo假設頂點v不在樹中。可是至少含有一條邊和樹相連，那么edgeTo[v] 就是將v和樹連接的最小權重的邊。而這個distTo則是這條邊的權重。
將這類頂點v都保存在一條索引優先的隊列中，索引v關聯的值是edgeTo的邊的權值。

2）Kruskal算法：
思想：依照邊的權重順序來處理它們，依次將當前權值最小的邊加入生成樹的邊中（加入的邊不能和已經加入的邊構成環）直至加入了V-1條邊。在整個過程中，加入的邊組成的森林隨著新加入的邊漸漸合成一棵樹。

使用一個優先隊列來將全部的邊（也就是為全部邊依照權值排序），然后再使用union-find數據結構識別新加入的邊是否會和已有的樹中的邊形成環（因為這是在動態處理中識別環是否存在，這里使用union-find（因為深度優先算法須要預處理整個圖，在這里不是非常適用）。最后用一個隊列或者別的數據結構來保存最小生成樹的全部邊。

三.最短路徑算法：

在詳細實現中使用到的類型結構；
1） 帶有權重的有向邊：

public class DirectedEdge {private int v;private int w;private double weight;public DirectedEdge(int v, int w, double weight) {this.v = v;this.w = w;this.weight = weight;}public int form() {return v;}public int to() {return w;}double weight() {return weight;} }

2） 加權有向圖：

public class EdgeWeightDigraph {private int V;private int E;public List<DirectedEdge>[] adj;public EdgeWeightDigraph(int V) {this.V = V;this.E = 0;adj = new ArrayList[V];for (int v = 0; v < V; v++) adj[v] = new ArrayList<>();}public int V() {return V;}public int E() {return E;}public void addEdge(DirectedEdge edge) {adj[edge.to()].add(edge);E++;}public List<DirectedEdge> adj(int v) {return adj[v];}public List<DirectedEdge> edges(){List<DirectedEdge> list=new ArrayList<>();for(int v=0;v<V;v++)for(DirectedEdge temp:adj[v])list.add(temp);return list;} }

在詳細實踐中用到的數據結構：
1） 最短路徑樹的邊：edgeTo[v]:由頂點索引的DirectedEdge的數組，當中edgeTo[v]的值是樹中連接v和它的父節點的邊
2） 到達起點的距離：distTo[]數組當中distTo[v]代表從點v到達起點的已知的最短路徑。
邊的松弛：
最短路徑的API都基于一個松弛操作，放松邊v→w意味著檢查從s(起點)到w的最短輪徑是否先到達v。再從v→w,假設是，則依據這個情況來跟新數據結構的內容。

也就是，那么distTo[v]與邊v→w邊的權重的和就可能成為新的s到達w的最短路徑。而且跟新distTo[v]，也就是說distTo[v]+e(vw).weight < distTo[w]，否則就說這條邊失效了，忽略它。
頂點的松弛：
將一個頂點所連接的全部邊進行松弛操作(這里的邊松弛和上述過程一樣)。

1）Dijkstra算法：
該算法採用了的思想和在求最小生成樹時候使用的prim算法相似的思想。首先將distTo[s]設置為0。distTo的其它元素設置為正無窮大，然后將distTo中最小的非樹頂點放松并加入到樹中，如此這般，直至全部頂點都在樹中。或者全部非樹頂點的distTo都無窮大。
Dijkstra能解決邊權值非負的加權的有向圖的最短路徑問題：

public class Dijkstra {private DirectedEdge[] edgeTo;public double distTo[];private IndexMinPQ<Double> pq;private boolean flag = false;public Dijkstra(EdgeWeightDigraph G, int s) {edgeTo = new DirectedEdge[G.V()];distTo = new double[G.V()];for (int v = 0; v < G.V(); v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[s] = 0.0;pq = new IndexMinPQ<>();pq.insert(s, 0.0);while (!pq.isEmpty()) {int v = pq.delMin();relax(G, v);/** 求解給定兩點的最短路徑* if (v == t) {flag = true;break;}*/}}private void relax(EdgeWeightDigraph G, int v) {for (DirectedEdge edge : G.adj[v]) {int w = edge.to();if (distTo[w] > distTo[v] + edge.weight()) {distTo[w] = distTo[v] + edge.weight();edgeTo[w]=edge;if (pq.contains(w))pq.change(w, distTo[w]);elsepq.insert(w, distTo[w]);}}}public Deque<DirectedEdge> pathTo(int t) {if (!hasPath(t))return null;Deque<DirectedEdge> list=new ArrayDeque<>();for(DirectedEdge edge=edgeTo[t];edge!=null;edge=edgeTo[edge.from()])list.push(edge);return list;}private boolean hasPath(int t) {return distTo[t]<Double.POSITIVE_INFINITY;} }

2）無環加權有向圖中的最短路徑算法：
對照Dijstra算法來說。對于無環加權有向圖的最短路徑有個好的改進算法，該算法：
a） 能夠在線性時間內解決單點最短路徑；
b） 能夠處理權值為負的邊
c） 能夠解決相關問題（譬如，最長路徑求解）
這些都是在無環有向圖的拓撲排序算法的簡單擴展。特別的是，將頂點放松和拓撲排序結合起來就能得到這樣的解決無環加權有向圖的最短路徑的簡單算法。

首先將distTo[s]初始化為0。其它distTo數組元素初始化正無窮大，然后依照拓撲排序來一個個放松頂點。（這樣的方法能在于V+E成正比的時間內解決無環加權有向圖的最短路徑問題）
對于無環問題來說，這樣的拓撲排序和放松相結合的算法，大大簡化了問題的推斷，而且這樣的算法和邊的權值的正負無關。可是僅僅能適用于無環結構（有環結構不能進行拓撲排序）。

import java.util.ArrayDeque; import java.util.Deque;public class Dijkstra {private DirectedEdge[] edgeTo;private double distTo[];public Dijkstra(EdgeWeightDigraph G, int s) {edgeTo = new DirectedEdge[G.V()];distTo = new double[G.V()];for (int v = 0; v < G.V(); v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[0] = 0;Topological top = new Topological(G);Deque<Integer> dp = top.order();for (int v = 0; v < G.V(); v++) {relax(G, dp.poll());}}private void relax(EdgeWeightDigraph G, Integer w) {for (DirectedEdge edge : G.adj[w])if (distTo[edge.to()] > distTo[w] + edge.weight()) {distTo[edge.to()] = distTo[w] + edge.weight();edgeTo[edge.to()] = edge;}}public double distTo(int v) {return distTo[v];}public boolean hasPath(int v) {return distTo[v] < Double.POSITIVE_INFINITY;}public Deque<DirectedEdge> pathTo(int v) {if (!hasPath(v))return null;else {Deque<DirectedEdge> list = new ArrayDeque<>();for (DirectedEdge s = edgeTo[v]; s != null; s = edgeTo[s.form()])list.push(s);return list;}} }

使用上面的算法還能高速的解決無環加權有向圖的單點最長路徑問題。解決無環加權有向圖的最長路徑問題須要的時間和E+V成正比。（證明，復制原來的無環加權有向圖的一個副本，并把副本中的全部邊的權值取相反數，這樣副本中的最短路徑就是原圖中的最長路徑。事實上在、實現的一個更簡單的方法就是。將distTo的初始值變為負無窮，然后改變松弛的條件方向）
對于這個算法還能夠運用在優先級限制下的并行任務調度（這就是個無環加權有向圖）：
問題描寫敘述：給定一組須要完畢的任務及其須要完畢的時間。一級乙組關于任務完畢的優先級限制順序。在滿足優先級限制的條件下，應該怎樣在若干個處理器上安排任務并在最短的時間內完畢全部的任務。

存在一個線性時間內的算法“關鍵路徑的方法被證明和無環加權有向圖的最長路徑問題是等價的。
解決并行任務調度的關鍵路徑方法的過程例如以下：創建一副無環加權的有向圖，當中包括一個起點s和一個終點t且每一個任務都相應著兩個頂點（一個起始頂點，一個任務結束頂點，兩個頂點間邊的長度為任務完畢所須要的時間）對于每條優先級限制v→w加入一條從v到w的權重為0的邊，還須要為每一個任務加入一個從起始點s指向該任務的起始點的權重為0的邊，以及一條從該任務的結束點到達終點t的權重為0的邊。這樣。每一個任務的估計開始時間就是從起始點s到達該任務起始點的最長距離。

3）一般加權有向圖中的最短路徑算法（BellmanFord算法）：
思想：在隨意含有V個頂點的加權有向圖中給定起始點s，從s無法到達不論什么負權重環，下面算法就能解決當中的單點最短路徑問題，將distTo[s]初始化為0，其它元素的distTo初始化為正無窮大。然后以隨意順序放松有向圖中的全部邊，反復V輪。

可是依據經驗，我們會非常easy的得出，隨意一輪中很多邊的放松都不會成功。僅僅有上一輪中distTo值發生變化的頂點連接的邊才干夠改變其它distTo中的元素值，我們能夠使用FIFO隊列來紀錄發生變化的頂點。

實現的時候使用下面兩種數據結構：
1）一條用來保存即將被放松的頂點的隊列；
2）一個由頂點索引的boolean數組。用來指示頂點是否在隊列中，防止反復的往隊列中加入頂點。
為了完整的實現V輪候算法能夠終止。實現這個目的一種方法就是顯示的紀錄輪數。

負權重值的檢測

轉載于:https://www.cnblogs.com/yangykaifa/p/7382862.html

總結

以上是生活随笔為你收集整理的图类算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。