# Graph - 圖 圖的表示通常使用**鄰接矩陣和鄰接表**，前者易實現但是對于稀疏矩陣會浪費較多空間，后者使用鏈表的方式存儲信息但是對于圖搜索時間復雜度較高。 ### 編程實現 ### 鄰接矩陣 設頂點個數為 V, 那么鄰接矩陣可以使用 V × V 的二維數組來表示。 ~~~ /* Java Definition */ int[][] g = new int[V][V] ~~~ `g[i][j]`表示頂點`i`和頂點`j`的關系，對于無向圖可以使用0/1表示是否有連接，對于帶權圖則需要使用`INF`來區分。有重邊時保存邊數或者權值最大/小的邊即可。 ### 鄰接表 鄰接表通過表示從頂點`i`出發到其他所有可能能到的邊。 ### Java 有向圖。 ~~~ /* Java Definition */ class DirectedGraphNode { int label; ArrayList<DirectedGraphNode> neighbors; DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); } } ~~~ 無向圖同上，只不過在建圖時雙向同時加。 ~~~ class UndirectedGraphNode { int label; ArrayList<UndirectedGraphNode> neighbors; UndirectedGraphNode(int x) { this.label = x; this.neighbors = new ArrayList<UndirectedGraphNode>(); } } ~~~