如何用java实现图的存储【邻接矩阵】

您所在的位置：网站首页 › 邻接矩阵表示法创建无向图 › 如何用java实现图的存储【邻接矩阵】

如何用java实现图的存储【邻接矩阵】

2023-07-29 15:23| 来源: 网络整理| 查看: 265

如何用java实现图的存储【邻接矩阵】首先得考虑图的几条重要特性如何表示顶点如何表示边表示图中的边有两种方法，邻接矩阵和邻接表。如何构造邻接矩阵如何把图打印出来看看结果附上代码完结撒花

首先得考虑图的几条重要特性

怎么样可以确定一个图呢，我们先举个例子：如图所示，该图中有5个顶点，“A” “B” “C” “D” “E”。而且A-B，A-D，B-D，B-C，D-E之间有一条边，事实上边上还可以有权值。

打个比方，顶点好比地图上的一个个城市，顶点间的边好比城市间的一条条公路，而边上的权值好比公路的长度（也就是城市间的距离）。

所以我们看到，要描述一个图，我们得用合适的方法表示好图的顶点，图上的边以及边的权值。

如何表示顶点

1.我们看到图中的顶点是由字母组成的，因此用一维集合ArrayList来存储顶点字母，这样顶点的个数也可以用ArrayList内部方法求得。

先定义ArrayList类：在这里插入图片描述定义一个String类数组利用增强for循环往ArrayList类添加结点：

这样图中顶点就表示完毕了

2.如何图省事的话直接： char数组也可以，不过只能存放单个字符如图（用于展示char数组，与本题图无关）在这里插入图片描述

如何表示边表示图中的边有两种方法，邻接矩阵和邻接表。

如图：邻接表前者适合稠密图，后者适合稀疏图。这里介绍用邻接矩阵实现：

在图中，一条边得由两个顶点决定。因此，要表示一条边，得注明两边的顶点是哪些；

所以我们用二维数组来存储边，二维数组的行数和列数都是顶点的个数，二维数组中的值代表该行（某顶点）该列（某顶点）下的边的情况。

这里，我用0代表两顶点间无边，大于0的树值代表边的权值。

如何构造邻接矩阵

有两种方法： 1.根据边的情况在初始化时写好二维数组，例如：在这里插入图片描述 2.也可以自行输入添加边（比较灵活）：首先定义一个二维数组：因为一条边是由两顶点确定的，我们无法直接求得边的条数，所以要加个变量numOfEdges: 现在要写添加边的函数（insertEdge）了：形参当然是三个，两个顶点+自身权值；

这里我们得注意：因为用二维数组表示图，必须让图中顶点对应相应的行和列；

比如这里0->“A” 1->“B” 2->“C” 3->“D” 4->“E”；也可以是其他对应方式，但最好容易辨认；

这里推荐两种方式：

graph.insertEdge(0,1,1);//A-B graph.insertEdge(0,3,1);//A-D graph.insertEdge(1,2,1);//B-C graph.insertEdge(1,3,1);//B-D graph.insertEdge(3,4,1);//D-E public void insertEdge(int v1,int v2,int weight){ edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }

或者一下方式更加直观：

graph.insert_char_Edge("A","B",1); graph.insert_char_Edge("A","D",1); graph.insert_char_Edge("B","C",1); graph.insert_char_Edge("B","D",1); graph.insert_char_Edge("D","E",1); public void insert_char_Edge(String a,String b,int weight){ int v1 = vertexList.indexOf(a);//返回对应的下标 int v2 = vertexList.indexOf(b);//返回对应的下标 edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }

个人觉得：java写出来的代码比C++工整美观很多。

如何把图打印出来

就是如何把我们构造好的邻接矩阵（二维数组）打印出来这里给大家介绍一个技巧，就是用增强for循环来打印二维数组。

// 显示图对应的矩阵 public void showGraph(){ for(int[]link:edges){ System.out.println(Arrays.toString(link)); } } 看看结果

在这里插入图片描述

附上代码 package graphic; import java.util.ArrayList; import java.util.Arrays; /** * @author Huadan Wang * @data 2020/5/6 - 11:49 */ public class Graph_2 { private static ArrayList vertexList;//存储顶点集合 private int [][] edges;//存储图对应的邻接矩阵 private int numOfEdges;//表示边的数目 public static void main(String[] args) { // 测试一把图是否创建 int n = 5;//结点的个数 String Vertexs[] = {"A","B","C","D","E"}; // 创建图对象 Graph_2 graph= new Graph_2(n); // 循环添加顶点 for(String vertex : Vertexs){ graph.insertVertex(vertex); } graph.insert_char_Edge("A","B",1); graph.insert_char_Edge("A","D",1); graph.insert_char_Edge("B","C",1); graph.insert_char_Edge("B","D",1); graph.insert_char_Edge("D","E",1); //显示一把邻接矩阵 graph.showGraph(); } //插入结点 public void insertVertex(String vertex) { vertexList.add(vertex); } public Graph_2(int n){ // 初始化矩阵和vertexList edges = new int[n][n]; vertexList = new ArrayList(n); numOfEdges = 0; } // 显示图对应的矩阵 public void showGraph(){ for(int[]link:edges){ System.out.println(Arrays.toString(link)); } } //添加边 public void insert_char_Edge(String a,String b,int weight){ int v1 = vertexList.indexOf(a); int v2 = vertexList.indexOf(b); edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } } 完结撒花

【本文地址】

如何用java实现图的存储【邻接矩阵】

如何用java实现图的存储【邻接矩阵】

今日新闻

推荐新闻