- 浏览: 55338 次
- 性别:
- 来自: 郑州
文章分类
最新评论
-
咖啡骑士:
亲测有效,谢谢了,转一下哦
mybatis创建oracle触发器的问题 -
ocaicai:
我遇到的问题是:批量更新1000条数据,居然使用了13秒,在百 ...
jdbcTemplate.batchUpdate没有批量执行
邻接矩阵表示的带权图。。。
首先创建了一个带权值的边类,在图中插入图的权值,所谓权值就是边上的数字,可以表示两个顶点之间的边的含义(可以是距离,路费。。。)
其次创建邻接矩阵带权图类,在此类中用到的SeqList<T>是我前几天所写的一个顺序表类,主要是用来存放顶点集合的,可以自己定义也可以用jdk中给的顺序表
输出结果如下(其中"$"表示最大权值)
首先创建了一个带权值的边类,在图中插入图的权值,所谓权值就是边上的数字,可以表示两个顶点之间的边的含义(可以是距离,路费。。。)
public class Edge implements Comparable<Edge> { public int start,dest,weight; public Edge(int start,int dest,int weight){ this.start = start; this.dest = dest; this.weight = weight; } public String toString(){ return "("+start+","+dest+","+weight+")"; } public int compareTo(Edge e) { // TODO Auto-generated method stub if(this.start!=e.start) return this.start - e.start; return this.dest - e.dest; } }
其次创建邻接矩阵带权图类,在此类中用到的SeqList<T>是我前几天所写的一个顺序表类,主要是用来存放顶点集合的,可以自己定义也可以用jdk中给的顺序表
public class AdjMatrixGraph<T> { protected SeqList<T> vertexlist; //顺序表存储的顶底集合 protected int[][] adjmatrix; //图的邻接矩阵,用二维数组表示 private final int MAX_WEIGHT = 99999; //设置最大权值,设置成常量 public AdjMatrixGraph(int size){ size = size<10?10:size; this.vertexlist = new SeqList<T>(size); //构造容量为size的空顺序表 this.adjmatrix = new int[size][size]; for(int i=0;i<size;i++){ //初始化邻接矩阵 for(int j=0;j<size;j++){ this.adjmatrix[i][j] = (i==j)?0:MAX_WEIGHT; } } } public AdjMatrixGraph(T[] vertices,Edge[] edges){ this(vertices.length); if(vertices == null) return; for(int i=0;i<vertices.length;i++) insertVertex(vertices[i]); if(edges!=null) for(int j=0;j<edges.length;j++) insertEdge(edges[j]); } public int vertexCount(){return this.vertexlist.length();} //返回定点顺序表的元素个数 public T get(int i){return this.vertexlist.get(i);} //返回第i个定点的元素 public int getWeight(int i,int j){return this.adjmatrix[i][j];} //返<vi,vj>边的权值 public String toString(){ String str = "顶点集合:"+this.vertexlist.toString()+"\n邻接矩阵:\n"; int n = this.vertexCount(); for(int i=0;i<n;i++){ for(int j=0;j<n;j++) str += this.adjmatrix[i][j] == MAX_WEIGHT?" $":" "+this.adjmatrix[i][j]; str +="\n"; } return str; } public int insertVertex(T x){ this.vertexlist.append(x); //顺序表追加元素,自动扩充 if(this.vertexCount()>this.adjmatrix.length){ //若二维数组不足,则扩充 int temp[][] = adjmatrix,i,j; //定义了局部变量i,j; this.adjmatrix = new int[temp.length*2][temp.length*2]; //二维数组扩充2倍 for(i=0;i<temp.length;i++){ for(j=0;j<temp.length;j++) this.adjmatrix[i][j] = temp[i][j]; for(j=temp.length;j<temp.length*2;j++) this.adjmatrix[i][j] = MAX_WEIGHT; } for(i=temp.length;i<temp.length*2;i++) for(j=0;j<temp.length*2;j++) this.adjmatrix[i][j] = (i == j)?0:MAX_WEIGHT; } return this.vertexlist.length()-1; //返回插入顶点的序号 } public void insertEdge(int i,int j,int weight){ //插入一条边 int n = this.vertexCount(); if(i>=0&&i<n&&j>=0&&j<n&&this.adjmatrix[i][j]==MAX_WEIGHT&&i!=j) this.adjmatrix[i][j] = weight; } public void insertEdge(Edge edge){ this.insertEdge(edge.start, edge.dest, edge.weight); } public void removeEdge(int i,int j){ //删除一条边 if(i>=0&&i<vertexCount()&&j>=0&&j<vertexCount()&&i!=j) this.adjmatrix[i][j] = MAX_WEIGHT; } public void removeVertex(int i){ //删除顶点以及和顶点有关系的边 int n = this.vertexCount(); if(i<0||i>n) return; this.vertexlist.remove(i); for(int j=0;j<i;j++) for(int k=i+1;k<n;k++) this.adjmatrix[j][k-1] = this.adjmatrix[j][k]; //元素向左移一行 for(int j=i+1;j<n;j++) for(int k=0;k<i;k++) this.adjmatrix[j-1][k] = this.adjmatrix[j][k]; //元素向上移一行 for(int j=i+1;j<n;j++) for(int k=i+1;k<n;k++) this.adjmatrix[j-1][k-1] = this.adjmatrix[j][k]; } public static void main(String[] args){ String[] verices = {"A","B","C","D","E"}; Edge edges[] = {new Edge(0,1,5),new Edge(0,3,2),new Edge(1,0,5), new Edge(1,2,7),new Edge(1,3,6),new Edge(2,1,7), new Edge(2,3,8),new Edge(2,4,3),new Edge(3,0,2), new Edge(3,1,6),new Edge(3,2,8),new Edge(3,4,9), new Edge(4,2,3),new Edge(4,3,9)}; AdjMatrixGraph<String> graph = new AdjMatrixGraph<String>(verices,edges); System.out.println("带权无向图"+graph.toString()); System.out.println("插入顶点F,插入边(A,F,9),删除顶点C,删除边(D,E)"); int i = graph.insertVertex("F"); graph.insertEdge(0,i,9); graph.insertEdge(i,0,9); graph.removeVertex(2); graph.removeEdge(2, 3); graph.removeEdge(3, 2); System.out.println(graph.toString()); } }
输出结果如下(其中"$"表示最大权值)
带权无向图顶点集合:A B C D E 邻接矩阵: 0 5 $ 2 $ 5 0 7 6 $ $ 7 0 8 3 2 6 8 0 9 $ $ 3 9 0 插入顶点F,插入边(A,F,9),删除顶点C,删除边(D,E) 顶点集合:A B D E F 邻接矩阵: 0 5 2 $ 9 5 0 6 $ $ 2 6 0 $ $ $ $ $ 0 $ 9 $ $ $ 0
发表评论
-
javaIO包
2014-02-26 14:30 756Java IO流: 流是一组有 ... -
java多线程
2014-02-26 14:29 867Java多线程: 什么是进程?{ 当前正在运行的程序。 代表 ... -
java集合
2014-02-26 14:28 1377Java中的集合: 为什么出现集合类? 面向对象语言对事物的体 ... -
java包
2014-01-26 17:59 713Java包:(package) 1.对 ... -
java内部类
2014-01-26 17:58 637Java内部类: 内部类:内置类,嵌套类。 将类定义在另一 ... -
java语法
2014-01-26 17:57 6341.java类命名规则? java中的关键字不能够作为类名, ... -
java异常
2014-01-26 17:55 732Java异常 什么是异常? ... -
java面向对象
2014-01-19 20:24 638什么是面向对象? 面向 ... -
java数组
2014-01-19 20:22 634什么是数组? 就是同一种类型数据的集合,其实就是 一个容器。 ... -
java中的运算符
2014-01-19 20:14 507Java运算符? Java中进行运算时所需要运用到的一些符号。 ... -
java中的流程控制
2014-01-19 20:12 686Java中有四类流程控制 判断结构 选择结构 循环结构 顺序结 ... -
java应用程序与数据库的连接
2013-05-30 02:31 747java应用程序与数据库的连接 Java数据库连接,(Jav ... -
java网络编程
2013-05-29 17:07 629java网络编程如果在一台机器上可以用到一个回文地址做测试,1 ... -
线程通讯问题
2013-05-15 17:01 633//有一个数据存储空间,划分为两部分,一部分用于存储人的姓 ... -
java线程锁定当前对象
2013-05-12 15:44 684java实现线程同步,如果有多个线程同时进行,那么程序很有可能 ... -
关于127.0.0.1 IP地址
2013-04-11 11:32 1439回送地址:127.0.0.1。一般用于测试使用。例如:ping ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1663164
1)实现图的邻接矩阵和邻接表存储结构; 2)完成基于邻接矩阵的深度优先搜索遍历及广度优先搜索遍历; 3)实现从键盘输入任意一对顶点,求出顶点间的最短路径。
图的邻接矩阵实现,用邻接矩阵实现了图,基本操作,主要算法
图的邻接矩阵和邻接表存储形式,并实现深度优先遍历和广度优先遍历
通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、循环链表、栈的基本概念、链式堆栈、中缀表达式、队列、链式队列、串、MyString、Brute-Force算法、MySet类实现、矩阵类、递归算法、哈夫曼...
数据结构 图 (邻接矩阵) java图形界面 实现 图的深度优先遍历算法 广度遍历算法 删除增加顶点等
NULL 博文链接:https://128kj.iteye.com/blog/1663043
NULL 博文链接:https://128kj.iteye.com/blog/1745423
根据Geoda生成的gal文件手工形成邻接矩阵太麻烦,也容易产生误差、 用java写了个gal2WM的小程序,顾名思义,就是将Geoda gal文件转成Matlab能够处理的格式。 使用方法: 1、运行jar包 2、打开gal文件(gal文件参见...
如何用java实现图的存储【邻接矩阵】首先得考虑图的几条重要特性如何表示顶点如何表示边表示图中的边有两种方法,邻接矩阵和邻接表。如何构造邻接矩阵如何把图打印出来看看结果附上代码完结撒花 首先得考虑图的几条...
* 换行,输入邻接矩阵,对于不相邻的城市,用 ∞(无穷大)表示 * 换行 输入城市代号 (例如:1 5表示1号城市和5号城市的最短带权路径和) * 5 0 5 7 ∞ ∞ 5 0 12 3 8 7 12 0 6 20 ∞ 3 6 0 15 ∞ 8 20 15 0 2 ...
主要介绍了Java编程实现邻接矩阵表示稠密图代码示例,具有一定参考价值,需要的朋友可以了解下。
NULL 博文链接:https://128kj.iteye.com/blog/1694918
基于java数据结构实验基于邻接矩阵和邻接表的深度广度优先遍历图.pdf
Java邻接矩阵图 使用邻接矩阵的Java有向图实现。
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
主要介绍了Java语言描述存储结构与邻接矩阵代码示例,涉及Java存储结构,邻接矩阵,邻接表的介绍与比较,然后分享了邻接矩阵的Java实现等相关内容,具有一定借鉴价值,需要的朋友可以参考。
对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、十字链表、邻接多重表,任选其中...
C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 ...35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS 共42集,需要哪一块知识自己下,一集3积分
从包含邻接矩阵的输入文本文件中绘制图形的 Java 应用程序。 应用程序还可以检查图形是否是二部图。 ##Open File 此函数显示一个文件选择窗口控件,使用户能够选择文本文件作为应用程序的输入。 文本文件应该使用...