Java数据结构之图的领接矩阵详解
更新时间:2021年11月30日 21:02 点击:329 作者:
1.图的领接矩阵(Adjacency Matrix)存储结构
图的领接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一位数组存储图中顶点信息,一个二维数组(称为领接矩阵)存储图中的边或弧的信息。
举例
无向图
无向图的领接矩阵的第i行或第i列的非零元素个数正好是第i个顶点的度。
有向图
有向图的领接矩阵的第i行的非零元素个数正好是第i个顶点的出度,第i列的非零元素个数正好是第i个顶点的入度。
带权值的网图
2.图的接口类
3.图的类型,用枚举类表示
public enum GraphKind { UDG,DG,UDN,DN;//无向图、有向图、无向网、有向网 }
4.图的领接矩阵描述
对于一个具有n个顶点的图G,可以将图G的领接矩阵存储在一个二维数组中.
package Graph; /* 图的领接矩阵描述类 */ import java.util.Scanner; public class MyGraph implements IGraph { public final static int INFINITY = Integer.MAX_VALUE; private GraphKind kind; //图的标志 private int vexNum, arcNum; //图当前顶点和边数 private Object[] vexs; //顶点 private int[][] arcs; //邻接矩阵 public MyGraph() { //空参构造 this(null, 0, 0, null, null); } public MyGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs, int[][] arcs) { // 实参构造 this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; this.arcs = arcs; } @Override public void createGraph() { //创建新图 Scanner sc = new Scanner(System.in); System.out.println("请输入图的类型:"); GraphKind kind = GraphKind.valueOf(sc.next()); switch (kind) { case UDG: createUDG(); return; case DG: createDG(); return; case UDN: createUDG(); return; case DN: createDN(); return; } } private void createUDG() { //创建无向图 Scanner sc = new Scanner(System.in); System.out.println("请输入图的顶点数、图的边数:"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("请分别输入图的各个顶点"); for (int v = 0; v < vexNum; v++) //构造顶点函数 vexs[v] = sc.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; //初始化领接矩阵 System.out.println("请输入各个边的两个顶点及其权值:"); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); arcs[v][u] = arcs[v][u] = sc.nextInt(); } } private void createDG() { //创建有向图 } ; private void createUDN() { //创建无向网 } private void createDN() { //创建有向网 Scanner sc = new Scanner(System.in); System.out.println("请输入图的顶点数、图的边数:"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new Object[vexNum]; System.out.println("请分别输入图的各个顶点"); for (int v = 0; v < vexNum; v++) //构造顶点函数 vexs[v] = sc.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; //初始化领接矩阵 System.out.println("请输入各个边的两个顶点及其权值:"); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); arcs[v][u] = sc.nextInt(); } } @Override public int getVexNum() { return vexNum; //返回顶点数 } @Override public int getArcNum() { return arcNum; //返回边数 } @Override //返回v的第一个领接点,若v没有领接点返回-1; public Object getVex(int v) throws Exception { if (v < 0 && v >= vexNum) throw new Exception("第" + v + "个顶点不存在!"); return vexs[v]; <0v<vexNum } @Override public int locateVex(Object vex) { //顶点定位法 for (int v = 0; v < vexNum; v++) if (vexs[v].equals(vex)) return v; return 0; } @Override public int firstAdjVex(int v) throws Exception { //查找第一个领接点 if (v < 0 && v >= vexNum) throw new Exception("第" + v + "个顶点不存在!"); for (int j = 0; j < vexNum; j++) if (arcs[v][j] != 0 && arcs[v][j] < INFINITY) return j; return -1; } @Override public int nextAdjvex(int v, int w) { //查找下一个领接点 return 0; } public GraphKind getKind(){ //返回图标类型 return kind; } public int[][] getArcs() { //返回邻接矩阵的值 return arcs; } //返回顶点 public Object[] getVexs() { return vexs; } }
测试类
public static void main(String[] args) throws Exception { MyGraph M=new MyGraph(); //创建图空间 M.createGraph(); System.out.println("创建无向网的顶点个数为:"+M.getVexNum()); System.out.println("创建无向网的边个数为:"+M.getArcNum()); System.out.println("请输入要查找顶点的值:"); Scanner sc=new Scanner(System.in); Object top=sc.next(); System.out.println("要查找顶点"+top+"的值为:"+ M.locateVex(top)); System.out.println("请输入要查找顶点的索引:"); int x= sc.nextInt(); System.out.println("要查找位置"+x+"处的顶点值为:"+M.getVex(x) ); System.out.println("请输入邻接点的顶点的位置:"); int n= sc.nextInt(); System.out.println("要查找位置"+n+"处的顶点值为:"+M.firstAdjVex(n) ); } }
结果
以上就是Java数据结构之图的领接矩阵详解的详细内容,更多关于Java数据结构资料请关注猪先飞其它相关文章!
原文出处:https://blog.csdn.net/weixin_56462645/article/details/121607
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java连接数据库oracle中文乱码解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-05-16