Java数据结构图的领接矩阵举例分析
发表于:2024-10-20 作者:千家信息网编辑
千家信息网最后更新 2024年10月20日,本篇内容介绍了"Java数据结构图的领接矩阵举例分析"的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!1
千家信息网最后更新 2024年10月20日Java数据结构图的领接矩阵举例分析
本篇内容介绍了"Java数据结构图的领接矩阵举例分析"的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
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) 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数据结构图的领接矩阵举例分析"的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站,小编将为大家输出更多高质量的实用文章!
顶点
矩阵
输入
无向
个数
存储
接点
有向图
结构
结构图
两个
位置
元素
数组
点数
类型
数据
分析
信息
内容
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
互联网软件开发公司怎么盈利
软件开发前需要写哪些文档
河北it软件开发市场前景如何
斗商科技网络技术
查看国产服务器硬件配置
江苏华为服务器维修多少钱
我的世界启动器中的服务器
网络安全学校专业
中国法院网络安全和信息化工作
地府服务器
北京正规软件开发配置
电脑音响设备无法连接到服务器
怎样导出阿里云服务器的数据
oa软件开发代码
罪恶王冠在哪个服务器
网络安全大赛有用吗
喋血复仇换服务器
网络安全级别更改
数据库查询例题及答案
深圳市普利得软件开发
dx100以太网服务器功能
医院系统服务器
湖南软件职业学校的软件开发
研究网络安全和网络意识形态安全
大学生网络安全防范论文
如何保证用户服务器传输安全
北京引力互联网科技有限公司
广州有效的社交软件开发
形容软件开发人员的
四十岁还能做软件开发吗