1.1圖的概念
圖（Graph），是一種複雜的非線性表結構，圖的元素我們就叫做頂點（vertex），一個頂點可以與任意其他頂點建立連接關係，這種建立的關係叫做邊（edge），頂點相連接的邊的條數叫做度（degree） 。邊有方向的圖叫做有向圖 ，邊無方向的圖叫無向圖 。每條邊都有一個權重（weight），可以通過這個權重來表示 一些可度量的值 ，這樣的圖叫做帶權圖（weighted graph） 。
1.2 圖的存儲原理
1.2.1 鄰接矩陣存儲
圖最直觀的一種存儲方法就是，鄰接矩陣（Adjacency Matrix），鄰接矩陣的底層是一個二維數組。
如果是無向圖，如果頂點 i 與頂點 j 之間有邊，我們就將A[i][j]和 A[j][i]標記為 1。
如果是有向圖，如果頂點 i 到頂點 j 之間，有一條箭頭從頂點 i 指向頂點 j 的邊，那我們就將A[i][j]標記為 1。同理，如果有一條箭頭從頂點 j 指向頂點 i 的邊，我們就將 A[j][i]標記為 1 .
如果是帶權圖，數組中就存儲相應的權重。
1.2.2 鄰接矩陣的代碼實現
public class Graph {private List vertexList;//存儲點的鍊表 private int[][] edges;//鄰接矩陣，用來存儲邊,值是權值 private int numOfEdges;//邊的數目 public Graph(int n) { //初始化矩陣，一維數組，和邊的數目 edges=new int[n][n]; vertexList=new ArrayList(n); numOfEdges=0; } //得到結點的個數 public int getNumOfVertex() { return vertexList.size(); } //得到邊的數目 public int getNumOfEdges() { return numOfEdges; } //返回結點i的數據 public Object getValueByIndex(int i) { return vertexList.get(i); } //返回v1,v2的權值 public int getWeight(int v1,int v2) { return edges[v1][v2]; } //插入結點 public void insertVertex(Object vertex) { vertexList.add(vertex); } //插入邊 public void insertEdge(int v1,int v2,int weight) { edges[v1][v2]=weight; numOfEdges++; }}
1.2.3 鄰接表存儲
用鄰接矩陣來表示一個圖，雖然簡單、直觀，但是比較浪費存儲空間，對於無向圖來說，如果 A[i][j]等於 1，那 A[j][i]也肯定等於 1。實際上，我們只需要存儲一個就可以了。 如果我們存儲的是稀疏圖（Sparse Matrix），也就是說，頂點很多，但每個頂點的邊並不多，那鄰接矩陣的存儲方法就更加浪費空間了。針對上面鄰接矩陣比較浪費內存空間的問題，有另外一種圖的存儲方法，鄰接表（Adjacency List）。
存儲原理
每個頂點對應一條鍊表，鍊表中存儲的是與這個頂點相連接的其他頂點。圖中畫的是一個有向圖的鄰接表存儲方式，每個頂點對應的鍊表裡面，存儲的是指向的頂點。 前面的數組存儲的是所有的頂點，每一個頂點後面連接的塊代表前面頂點所指向的頂點和路線的權值。如果該點還指向其他頂點，則繼續在塊後面添加。例如A指向了B權值是4，那麼A後面就加上一塊，之後發現A還指向D權值是5，那麼就在塊尾繼續添加一塊。其實也就是數組+鍊表的結構.
1.2.4鄰接表代碼實現
根據鄰接表的結構和圖，圖其實是由頂點和邊組成的。抽象出兩種類，一個是Vertex頂點類，一個是Edge邊類
頂點
class Vertex{String name;//頂點名稱 Edge next;//從該定點出發的邊 public Vertex(String name, Edge edge) { this.name = name; this.next = edge; }}
邊：
class Edge{String name;//指向下一個頂點的名字 int weight;//權重 Edge next;//被指向的下一個邊 public Edge(String name, int weight, Edge next) { this.name = name; this.weight = weight; this.next = next; }}
添加和遍歷的實現
public class Graph2 {Map<String, Vertex> vertexsMap; Graph2(){ this.vertexsMap = new HashMap<>(); } /** * 添加頂點 * @param name 頂點名稱 */ public void insertVertex(String name) { Vertex vertex = new Vertex(name,null); vertexsMap.put(name,vertex); } /** * 插入變 * @param start 開始頂點名稱 * @param end 結束頂點名稱 * @param weight 權重 */ public void insertEdge(String start,String end,int weight){ //現獲取開始頂點 Vertex startVertex = vertexsMap.get(start); //開始頂點為null，直接返回，也可以新建一個頂點// if (startVertex==null){// return;// } if (startVertex==null){ startVertex = new Vertex(start,null); vertexsMap.put(start,startVertex); } //新建邊 Edge edge = new Edge(end, weight, null); if (startVertex.next==null){ startVertex.next=edge; }else{ //如果不為null 尋找節點的next==null的位置，掛上這個邊 Edge lastEdge = startVertex.next; while(lastEdge.next!=null){ lastEdge=lastEdge.next; } lastEdge.next=edge; } } public void print(){ Set<Map.Entry<String, Vertex>> set = vertexsMap.entrySet(); Iterator<Map.Entry<String, Vertex>> iterator = set.iterator(); while (iterator.hasNext()){ Map.Entry<String, Vertex> entry = iterator.next(); Vertex vertex = entry.getValue(); Edge edge = vertex.next; while(edge!=null){ System.out.println(vertex.name+"指向："+edge.name+"權重是："+edge.weight); edge= edge.next; } } } public static void main(String[] args) { Graph2 graph = new Graph2(); graph.insertVertex("A"); graph.insertVertex("B"); graph.insertVertex("C"); graph.insertVertex("D"); graph.insertVertex("E"); graph.insertVertex("F"); graph.insertEdge("C", "A", 1); graph.insertEdge("F", "C", 2); graph.insertEdge("A", "B", 4); graph.insertEdge("E", "B", 2); graph.insertEdge("A", "D", 5); graph.insertEdge("D", "F", 4); graph.insertEdge("D", "E", 3); graph.print(); }}
測試驗證：
按照此圖來存儲
先存儲A-F6個頂點，然後存7個邊：
1.3 圖的遍歷
遍歷是指從某個節點出發，按照一定的的搜索路線，依次訪問對數據結構中的全部節點，且每個節點僅訪問一次.
從給定圖中任意指定的頂點（稱為初始點）出發，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點，使每個頂點僅被訪問一次，這個過程稱為圖的遍歷。遍歷過程中得到的頂點序列稱為圖遍歷序列
圖的遍歷可以分為2中策略：深度優先搜索 （DFS，Depth First Search ）、廣度優先搜索（BFS，Breadth First Search ）
1.3.1 深度優先搜索DFS
深度優先搜索，從起點出發，從規定的方向中選擇其中一個不斷地向前走，直到無法繼續為止，然後嘗試另外一種方向，直到最後走到終點。就像走迷宮一樣，儘量往深處走.
DFS 解決的是連通性的問題，即，給定兩個點，一個是起始點，一個是終點，判斷是不是有一條路徑能從起點連接到終點。起點和終點，也可以指的是某種起始狀態和最終的狀態。問題的要求並不在乎路徑是長還是短，只在乎有還是沒有。
遍歷過程
以下圖為例，需要依賴棧（Stack），特點是後進先出（LIFO）。
第一步選擇一個起始頂點，頂點A，把A壓棧標記它為訪問過（用紅色標記），並輸出到結果中。
第二步 尋找與 A 相連並且還沒有被訪問過的頂點，頂點 A 與 B、D、G 相連，而且它們都還沒有被訪問過，按照字母順序處理，所以將 B 壓入棧，標記它為訪問過，並輸出到結果中。
第三步，現在在頂點 B 上，重複上面的操作，由於 B 與 A、E、F 相連，如果按照字母順序處理的話，A 應該是要被訪問的，但是 A 已經被訪問了，所以我們訪問頂點 E，將 E 壓入棧，標記它為訪問過，並輸出到結果中
第四步，從 E 開始，E 與 B、G 相連，但是B剛剛被訪問過了，所以下一個被訪問的將是G，把G壓入棧，標記它為訪問過，並輸出到結果中
第五步，現在在頂點 G 的位置，由於與 G 相連的頂點都被訪問過了，類似於走到了一個死胡同，必須嘗試其他的路口了。所以這裡要做的就是簡單地將 G 從棧裡彈出，表示從 G 這裡已經無法繼續走下去了，看看能不能從前一個路口找到出路。
第六步，現在棧的頂部記錄的是頂點 E，來看看與 E 相連的頂點中有沒有還沒被訪問到的，發現它們都被訪問了，所以把 E 也彈出去。
第七步，當前棧的頂點是 B，看看它周圍有沒有還沒被訪問的頂點，有，是頂點 F，於是把 F 壓入棧，標記它為訪問過，並輸出到結果中。
第八步，當前頂點是 F，與 F 相連並且還未被訪問到的點是 C 和 D，按照字母順序來，下一個被訪問的 點是 C，將 C 壓入棧，標記為訪問過，輸出到結果中。
第九步，當前頂點為 C，與 C 相連並尚未被訪問到的頂點是 H，將 H 壓入棧，標記為訪問過，輸出到結 果中。
第十步，當前頂點是 H，由於和它相連的點都被訪問過了，將它彈出棧。
第十一步，當前頂點是 C，與 C 相連的點都被訪問過了，將 C 彈出棧
第十二步，當前頂點是 F，與 F 相連的並且尚未訪問的點是 D，將 D 壓入棧，輸出到結果中，並標記為 訪問過。
第十三步，當前頂點是 D，與它相連的點都被訪問過了，將它彈出棧。以此類推，頂點 F，B，A 的鄰居 都被訪問過了，將它們依次彈出棧就好了。最後，當棧裡已經沒有頂點需要處理了，我們的整個遍歷結 束。
時間複雜度
鄰接表：訪問所有頂點的時間為 O(V)，而查找所有頂點的鄰居一共需要 O(E) 的時間，所以總的時間複雜度是O(V + E)。
鄰接矩陣：查找每個頂點的鄰居需要 O(V) 的時間，所以查找整個矩陣的時候需要 O(V^2) 時間
1.3.2 廣度優先搜索 BFS
就是一種「地毯式」層層推進的搜索策略，即先查找離起始頂點最近的，然後是次近的，依次往外搜索.
遍歷過程
還是以下圖為例，需要依賴隊列（Queue），先進先出（FIFO），一層一層地把與某個點相連的點放入隊列中，處理節點的時候正好按照它們進入隊列的順序進行
第一步，選擇一個起始頂點，頂點 A 開始，把 A 壓入隊列，標記它為訪問過（用紅色標記）
第二步，從隊列的頭取出頂點 A，列印輸出到結果中，同時將與它相連的尚未被訪問過的點按照字母大小順序壓入隊列，同時把它們都標記為訪問過，防止它們被重複地添加到隊列中。
第三步，從隊列的頭取出頂點 B，列印輸出它，同時將與它相連的尚未被訪問過的點（也就是 E 和 F）壓入隊列，同時把它們都標記為訪問過。
第四步，繼續從隊列的頭取出頂點 D，列印輸出它，此時我們發現，與 D 相連的頂點 A 和 F 都被標記訪問過了，所以就不要把它們壓入隊列裡
第五步，接下來，隊列的頭是頂點 G，列印輸出它，同樣的，G 周圍的點都被標記訪問過了，不做任何處理。
第六步，隊列的頭是 E，列印輸出它，它周圍的點也都被標記為訪問過了，不做任何處理。
第七步，接下來輪到頂點 F，列印輸出它，將 C 壓入隊列，並標記 C 為訪問過。
第八步，將 C 從隊列中移出，列印輸出它，與它相連的 H 還沒被訪問到，將 H 壓入隊列，將它標記為訪問過。
第九步，隊列裡只剩下 H 了，將它移出，列印輸出它，發現它的鄰居都被訪問過了，不做任何事情。
第十步，隊列為空，表示所有的點都被處理完畢了，程序結束
廣度優先一般是用於查找最短路徑問題。
時間複雜度
鄰接表：每個頂點都需要被訪問一次，時間複雜度是 O(V)；相連的頂點（也就是每條邊）也都要被訪問一次，加起來就是 O(E)。因此整體時間複雜度就是 O(V+E)
鄰接矩陣：V 個頂點，每次都要檢查每個頂點與其他頂點是否有聯繫，因此時間複雜度是O(v^2)
廣度優先的搜索可以同時從起始點和終點開始進行，稱之為雙端 BFS。這種算法往往可以大大地提高搜索的效率。