對于無向圖來說，如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。實際上，我們只需要存儲一個就可以了。 也就是說，無向圖的二維數組中，如果我們將其用對角線劃分為上下兩部分，那我們只需要利用上面或 者下面這樣一半的空間就足夠了，另外一半白白浪費掉了。
一、鄰接表
用鄰接矩陣來表示一個圖，雖然簡單、直觀，但是比較浪費存儲空間 。
對于無向圖來說，如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。實際上，我們只需要存儲一個就可以了。 也就是說，無向圖的二維數組中，如果我們將其用對角線劃分為上下兩部分，那我們只需要利用上面或 者下面這樣一半的空間就足夠了，另外一半白白浪費掉了。
還有，如果我們存儲的是稀疏圖（Sparse Matrix），也就是說，頂點很多，但每個頂點的邊并不多， 那鄰接矩陣的存儲方法就更加浪費空間了。比如微信有好幾億的用戶，對應到圖上就是好幾億的頂點。 但是每個用戶的好友并不會很多，一般也就三五百個而已。如果我們用鄰接矩陣來存儲，那絕大部分的 存儲空間都被浪費了 針對上面鄰接矩陣比較浪費內存空間的問題，我們來看另外一種圖的存儲方法，鄰接表（Adjacency List）。
每個頂點對應一條鏈表，鏈表中存儲的是與這個頂點相連接的其他頂點。
圖中畫的是一個有向圖的鄰接表存儲方式，每個頂點對應的鏈表里面，存儲的是指向的頂點。 前面的數組存儲的是所有的頂點，每一個頂點后面連接的塊代表前面頂點所指向的頂點和路線的權值。
如果該點還指向其他頂點，則繼續在塊后面添加。例如A指向了B權值是4，那么A后面就加上一塊，之 后發現A還指向D權值是5，那么就在塊尾繼續添加一塊。其實也就是數組+鏈表的結構。
根據鄰接表的結構和圖，我們不難發現，圖其實是由頂點和邊組成的。所以我們就抽象出兩種類，一個 是Vertex頂點類，一個是Edge邊類。
/**
* 頂點
*/
public class Vertex {
String name; //頂點名稱
Edge next; //從該定點出發的邊
public Vertex(String name, Edge next){
this.name = name;
this.next = next;
}
}
/**
* 邊
*/
public 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;
}
}
package graph;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
* 鄰接表實現
*/
public class Graph2 {
Map<String, Vertex> vertexsMap; //存儲所有的頂點
Graph2(){
this.vertexsMap = new HashMap<>();
}
public void insertVertex(String vertexName){ //添加頂點
Vertex vertex = new Vertex(vertexName, null);
vertexsMap.put(vertexName, vertex);
}
public void insertEdge(String begin, String end, int weight){
//添加弧
Vertex beginVertex = vertexsMap.get(begin);
if(beginVertex == null){
beginVertex = new Vertex(begin, null);
vertexsMap.put(begin, beginVertex);
}
Edge edge = new Edge(end, weight, null);
if(beginVertex.next == null){
beginVertex.next = edge;
}else{
Edge lastEdge = beginVertex.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();
}
}
