鄰接表

相比鄰接矩陣，鄰接表要更加節省空間。

鄰接表存儲

本文將介紹鄰接表存儲有向帶權圖。圖的例子如下。

圖

介紹一下鄰接表

上面的圖對應的鄰接表如下圖所示：

鄰接表

前面的數組存儲的是所有的頂點，每一個頂點后面連接的塊代表前面頂點所指向的頂點和路線的權值。如果該點還指向其他頂點，則繼續在塊后面添加。例如A指向了B權值是4，那么A后面就加上一塊，之后發現A還指向D權值是5，那么就在塊尾繼續添加一塊。其實也就是數組+鏈表的結構。

如何存儲呢？

根據鄰接表的結構和圖，我們不難發現，圖其實是由頂點和弧組成的。所以我們就抽象出兩種類，一個是Vertex頂點類，一個是Edge弧類。

Vertex類，包括頂點的名字，和從頂點出發的弧。代表數組

private class Vertex{

private String name; //頂點名稱

private Edge next; //從該定點出發的弧

}

Edge類，包括被指向頂點的名稱，弧的權值，下一個弧。

private class Edge{

private String name; //被指向的頂點

private int weight; //弧的權值

private Edge next; //被指向的下一段弧

}

上圖中的數組中的元素就是Vertex，后面接上塊就是Edge。

完整代碼如下

代碼使用HashMap集合存儲頂點。對于輸入的弧，頂點如果不存在則添加新的頂點。讀者可以自己進行查看。

/**

* 有向帶權圖

* Created by ShouJingGuo on 2018/3/27.

*/

public class Graph {

Map vertexsMap; //存儲所有的頂點

private class Vertex{

private String name; //頂點名稱

private Edge next; //下一段弧

Vertex(String name, Edge next){

this.name = name;

this.next = next;

}

}

private class Edge{

private String name; //被指向頂點名稱

private int weight; //弧的權值

private Edge next; //下一段弧

Edge(String name, int weight, Edge next){

this.name = name;

this.weight = weight;

this.next = next;

}

}

Graph(){

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> set = vertexsMap.entrySet();

Iterator> iterator = set.iterator();

while(iterator.hasNext()){

Map.Entry 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) {

Graph graph = new Graph();

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();

}

}

總結

以上是生活随笔為你收集整理的java邻接图_Java数据结构 - 图（邻接表存储）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。