出處:https://segmentfault.com/a/1190000038518587
為什麼要有圖？1、前面我們學習到的線性表與樹
2、線性表侷限一個直接前驅和一個直接後續的關係
3、樹也只能有一個直接前驅、也就是父節點
4、我們需要多對多的關係的時候，就需要使用到圖
一、什麼是圖圖的基本介紹圖是一種資料結構，其中結點可以具有零個或多個相鄰元素，兩個節點之間的連線稱為邊、結點也可以稱為頂點
圖的常用知識概念圖的常見表達方式圖的表達方式有兩種： 二維陣列表示（領接矩陣）；連結串列表示（鄰接表）
頂點0 ->頂點1、2、3、4、5、時，若能連通則是1，否則0 表示
二、透過示例認識圖圖的快速入門案例根據如圖所示，使用鄰接矩陣展示連線效果，1 表示能連線 0-表示不能連線
思路分析1.使用集合的方式儲存節點資訊
2.使用二維陣列[][]儲存矩陣資訊
4.新增兩個節點之間的連線時，需要記錄兩個節點的下標
public class Graph { private ArrayList<String > vertexList;//儲存頂點的集合 private int[][] edges;//儲存頂點對應圖的鄰接矩陣 private int numOfEdges;//表示邊的數目 //構造器 public Graph(int n ){ edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; } //插入節點 public void insertVertex(String vertex){ vertexList.add(vertex); } //新增邊 public void insertEdge(int v1,int v2,int weight){ edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } //返回目前的節點個數 public int getNumOfVertex(){ return vertexList.size(); } //得到目前邊的個數 public int getNumOfEdges(){ return numOfEdges; } //返回下標對應節點資料 public String getValueByIndex(int i){ return vertexList.get(i); } //返回兩個節點之間的權值 public int getWeight(int v1,int v2){ return edges[v1][v2]; } //顯示圖對應的矩陣 public void showGraph(){ for(int[] link :edges){ System.out.println(Arrays.toString(link)); } }}接下來我們按照圖所示，將節點：A、B、C、D、E 新增進demo看看
public static void main(String[] args) { //節點的陣列 String[] arr = {"A","B","C","D","E"}; //建立圖物件 Graph graph = new Graph(arr.length); //迴圈新增頂點項 for(String data :arr){ graph.insertVertex(data); } graph.showGraph();}執行結果如下：[0, 0, 0, 0, 0][0, 0, 0, 0, 0][0, 0, 0, 0, 0][0, 0, 0, 0, 0][0, 0, 0, 0, 0]根據執行結果來說，我們新增成功了，但是發現了嘛？為什麼全是0？
那是我們沒有新增邊，並且如圖所示是 無向圖 ，現在我們進行新增邊
如圖連線的節點是： A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B
public static void main(String[] args) { //節點的陣列 String[] arr = {"A","B","C","D","E"}; //建立圖物件 Graph graph = new Graph(arr.length); //迴圈新增頂點項 for(String data :arr){ graph.insertVertex(data); } //graph.showGraph(); //新增邊 //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B` graph.insertEdge(0,1,1);//`A-B graph.insertEdge(0,2,1);//`A-C graph.insertEdge(1,2,1);//`B-C graph.insertEdge(1,4,1);//`B-E graph.insertEdge(1,3,1);//`B-D graph.showGraph();}執行結果如下：[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]我們可以對比一下上面的圖，是否正確關聯起來
圖遍歷介紹所謂的圖遍歷，即是對結點的訪問。
一個圖有那麼多個結點，如何遍歷這些結點？
需要特定策略，一般有兩種訪問策略: (1)深度優先遍歷(2)廣度優先遍歷
三、圖的深度優先遍歷介紹圖的深度優先搜尋(Depth First Search)1.首先訪問第一個鄰接結點，然後 再以這個被訪問的鄰接結點 作為 初始結點 ，訪問 它的第一個鄰接結點
（每次都在訪問完當前結點後，再以之前訪問的當前結點的第一個鄰接結點）
2.這樣的訪問策略是優先往縱向挖掘深入，而不是對一個結點的所有鄰接結點進行橫向訪問
深度優先遍歷演算法步驟1.訪問 初始結點v ，並 標記結點v為已訪問2.查詢 結點v 的 第一個鄰接結點w
3.若 w存在 ，則繼續執行4，如果 w不存在 ，則回到第1步，將 從v的下一個結點 繼續
4.若w未被訪問，對w進行深度優先遍歷遞迴（即把 w當做另一個v，然後進行步驟123 ）
5.查詢結點v的w鄰接結點的下一個鄰接結點，轉到步驟3
以上面建立的圖，進行一個示例深度優先遍歷的圖解分析，假設初始點：A
引用示例圖解分析演算法步驟第一步：訪問初始結點v，並標記結點v為已訪問
第二步：查詢結點v的第一個鄰接結點w
第三步：若 w存在 ，則繼續執行，檢查若w是否未被訪問，則對w進行深度優先遍歷遞迴（即把 w當做另一個v，然後進行步驟123 ），如果 w不存在 ，則回到第1步，將 從v的下一個結點 繼續，
第四步：將w節點當做另一個v，執行步驟1-2-3
第五步：C的鄰接節點不存在，返回上一層，即是B節點，從下一個節點繼續
第六步：D的鄰接節點不存在，返回上一層，即是B節點，從下一個節點繼續
深度優先搜尋程式碼實現1.我們需要記錄某個節點是否被訪問
2.我們查詢節點V的鄰接節點W，需要知道w的下標，所以需要求出w的下標
根據我們前面的二維陣列以及遍歷思路，A的下一鄰接節點B，就是 [A][B] >0
// 得到領接節點的下標public int getFirstNeighbor(int index){ for (int j =0; j<vertexList.size() ; j++){ if(edges[index][j] > 0){ return j; } } return -1;}3.我們查詢新節點V的鄰接節點W，需要根據前一個鄰接節點的下標獲取
我們需要C的節點鄰接節點W，就需要前一個鄰接節點C的下標
//根據前一個鄰接節點的下標獲取下一個領接節點public int getNextNeighbor(int v1,int v2){ for (int j = v2 +1 ;j<vertexList.size();j++){ if(edges[v1][j] >0){ return j; } } return -1;}那麼按照圖解思路，我們的演算法方法程式碼（有缺陷，只能訪問一次）就是
public class Graph { //省略之前關鍵程式碼 private boolean[] isVisited;//記錄某個節點是否被訪問 //構造器 public Graph(int n ){ edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; isVisited = new boolean[n]; } //深度優先遍歷方法 public void dfs(boolean [] isVisited,int i ){ //輸出節點進行訪問 System.out.print(getValueByIndex(i) + " - >"); //標記已訪問 isVisited[i] = true; //查詢當前節點i的鄰接節點w int w = getFirstNeighbor(i); while(w != -1){ //鄰接節點w未被訪問 if(!isVisited[w]){ dfs(isVisited,w); } //如果w被訪問過了 w = getNextNeighbor(i,w); } } public void dfs(){ for(int j=0; j< getNumOfVertex(); j++){ if(!isVisited[j]){ dfs(isVisited,j); } } }我們根據之前新增的demo測試遍歷輸出看看
public static void main(String[] args) { //節點的陣列 String[] arr = {"A","B","C","D","E"}; //建立圖物件 Graph graph = new Graph(arr.length); //迴圈新增頂點項 for(String data :arr){ graph.insertVertex(data); } //graph.showGraph(); //新增邊 //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B` graph.insertEdge(0,1,1);//`A-B graph.insertEdge(0,2,1);//`A-C graph.insertEdge(1,2,1);//`B-C graph.insertEdge(1,4,1);//`B-E graph.insertEdge(1,3,1);//`B-D graph.showGraph(); graph.dfs();}執行結果如下：[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]A - >B - >C - >D - >E - >1.類似於一個分層搜尋的過程
2.廣度優先遍歷需要使用一個佇列以保持訪問過的結點的順序，以便按這個順序來訪問這些結點的鄰接結點
廣度優先遍歷演算法步驟1.訪問 初始結點v 並 標記 結點v為 已訪問 。
2.結點 v入佇列
3.當佇列 非空時繼續執行 ，否則 初始結點v的演算法 結束。
4.出佇列，取得 佇列頭結點u 。
5.查詢 結點u 的 第一個鄰接結點w 。
6.若結點u的 鄰接結點w不存在 ，則轉到 步驟3 ；
否則迴圈執行以下三個步驟：
6.1 若結點w尚 未被訪問 ，則訪問結點w並 標記為已訪問 。
6.2 把 結點w入佇列
6.3 接著查詢結點u的 繼w鄰接結點後 的 下一個鄰接結點 ，當做w轉到步驟6。
以上面建立的圖，進行一個示例廣度優先遍歷的圖解分析，假設初始點：A
引用示例圖解分析演算法步驟第一步：訪問初始結點v，並標記結點v為已訪問，並將節點v入佇列
第二步：此時出佇列，獲取佇列頭結點u，查結點u的第一個鄰接結點w
第三步：如果 w不存在 ，則回到第二步，查詢結點u的繼w的下一個 鄰接節點結點 繼續。若 w存在 ，則檢查w是否未被訪問，未訪問則對w進行標記訪問，並且 入佇列 ，且繼續查詢 繼w鄰接節點後的下一個節點 當做w，接著判斷
第四步:接著查詢結點u的 繼w鄰接結點後 的 下一個鄰接結點 ，當做結點w
第五步：如果 w不存在 ，則回到第二步，查詢結點u的繼w的下一個 鄰接節點結點 繼續。若 w存在 ，則檢查w是否未被訪問，未訪問則對w進行標記訪問，並且 入佇列 ，且繼續查詢 繼w鄰接節點後的下一個節點 當做w，接著判斷
第六步:接著查詢結點u的 繼w鄰接結點後 的 下一個鄰接結點 ，當做結點w
第七步：如果 w不存在 ，則回到第二步，查詢結點u的繼w的下一個 鄰接節點結點 繼續，直至結束回到思路的第二步，代表結點u（A）結束
第八步：出佇列，取得佇列頭結點U、進行查詢鄰接結點w
第九步：如果 w不存在 ，則回到第二步，查詢結點u的繼w的下一個 鄰接節點結點 繼續。若 w存在 ，則檢查w是否未被訪問，未訪問則對w進行標記訪問，並且 入佇列 ，且繼續查詢 繼w鄰接節點後的下一個節點 當做w，接著判斷
第十步：接著查詢結點u的 繼w鄰接結點後 的 下一個鄰接結點 ，當做結點w
第十一步：如果 w不存在 ，則回到第二步，查詢結點u的繼w的下一個 鄰接節點結點 繼續。若 w存在 ，則檢查w是否未被訪問，未訪問則對w進行標記訪問，並且 入佇列 ，且繼續查詢 繼w鄰接節點後的下一個節點 當做w，接著判斷
第十二步：如果 w不存在 ，則回到第二步，查詢結點u的繼w的下一個 鄰接節點結點 繼續，直至結束回到思路的第二步，代表結點u（B）結束
廣度優先搜尋程式碼實現1.我們可以先一個節點的廣度優先方法，其次其他節點迴圈呼叫即可
//對一個節點進行廣度優先遍歷方法public void bfs(boolean[] isVisited,int i ){ int u;//表示佇列頭節點的下標 int w;//表示鄰接節點的下標 //需要一個佇列記錄訪問的順序 LinkedList queue = new LinkedList(); //訪問節點，輸出節點資訊 System.out.print(getValueByIndex(i) + " ->"); isVisited[i] = true; //將節點加入佇列，記錄訪問順序 //佇列尾部新增，頭部取 queue.addLast(i); while (!queue.isEmpty()){ //取出佇列的頭結點，刪掉 u = (Integer) queue.removeFirst(); //查詢頭結點u的鄰接節點 w = getFirstNeighbor(u); //w != -1 代表找到鄰接節點 while(w!= -1 ){ //判斷是否訪問過 if(!isVisited[w]){ //若沒有訪問過，則輸出並標記已訪問 System.out.print(getValueByIndex(i) + " ->"); isVisited[w] = true; //將節點入佇列，代表訪問過 queue.addLast(w); } //以u為起點，查詢w鄰接結點的下一個鄰接結點 w = getNextNeighbor(u,w); } }}2.接下來則遍歷所有節點進行廣度優先搜尋
//廣度優先遍歷方法public void bfs(){ for(int j=0; j< getNumOfVertex(); j++){ //沒有被訪問過才進行廣度優先搜尋 if(!isVisited[j]){ bfs(isVisited,j); } }}我們根據之前新增的demo測試遍歷輸出看看
public static void main(String[] args) { //節點的陣列 String[] arr = {"A","B","C","D","E"}; //建立圖物件 Graph graph = new Graph(arr.length); //迴圈新增頂點項 for(String data :arr){ graph.insertVertex(data); } //graph.showGraph(); //新增邊 //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B` graph.insertEdge(0,1,1);//`A-B graph.insertEdge(0,2,1);//`A-C graph.insertEdge(1,2,1);//`B-C graph.insertEdge(1,4,1);//`B-E graph.insertEdge(1,3,1);//`B-D graph.showGraph(); //graph.dfs(); graph.bfs();}運算結果如下：[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]A ->B ->C ->D ->E ->作者:28640
出處:https://segmentfault.com/a/1190000038518587