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