java邻接图_Java数据结构 - 图（邻接表存储）

骑猪看日落 2022-11-07 15:55 241阅读 0赞

邻接表

相比邻接矩阵，邻接表要更加节省空间。

邻接表存储

本文将介绍邻接表存储有向带权图。图的例子如下。

![3b09a37cf16d][]

图

介绍一下邻接表

上面的图对应的邻接表如下图所示：

![3b09a37cf16d][]

邻接表

前面的数组存储的是所有的顶点，每一个顶点后面连接的块代表前面顶点所指向的顶点和路线的权值。如果该点还指向其他顶点，则继续在块后面添加。例如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();

[3b09a37cf16d]: /images/20221023/613b81f049384d5e96cd1407fbcce7dc.png

java邻接图_Java数据结构 - 图（邻接表存储）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关图存储之邻接多重表

相关图存储之邻接表法

相关 java邻接图_Java数据结构 - 图（邻接表存储）

相关数据结构—图的存储—邻接表和邻接矩阵

相关图的邻接多重表存储

相关【数据结构】图的存储--邻接表

相关图邻接表数组存储

相关邻接表来存储图

相关 java数据结构-----图（邻接矩阵和邻接表）

相关数据结构——图的存储（邻接表）