Java数据结构之图(动力节点Java学院整理)
1,摘要:
本文章主要讲解学习如何使用java语言以邻接表的方式实现了数据结构---图(graph)。从数据的表示方法来说,有二种表示图的方式:一种是邻接矩阵,其实是一个二维数组;一种是邻接表,其实是一个顶点表,每个顶点又拥有一个边列表。下图是图的邻接表表示。
从图中可以看出,图的实现需要能够表示顶点表,能够表示边表。邻接表指是的哪部分呢?每个顶点都有一个邻接表,一个指定顶点的邻接表中,起始顶点表示边的起点,其他顶点表示边的终点。这样,就可以用邻接表来实现边的表示了。如顶点v0的邻接表如下:
与v0关联的边有三条,因为v0的邻接表中有三个顶点(不考虑v0)。
2,具体分析
先来分析边表:
在图中如何来表示一条边?很简单,就是:起始顶点指向结束顶点、就是顶点对<startvertex, endvertex>。在这里,为了考虑边带有权值的情况,单独设计一个类edge.java,作为vertex.java的内部类,edge.java如下:
protected class edge implements java.io.serializable { private vertexinterface<t> vertex;// 终点 private double weight;//权值
edge类中只有两个属性,vertex 用来表示顶点,该顶点是边的终点。weight 表示边的权值。若不考虑带权的情况,就不需要weight属性,那么可以直接定义一个顶点列表 来存放 终点 就可以表示边了。这是因为:这些属性是定义在vertex.java中,而vertex本身就表示顶点,如果在vertex内部定义一个list存放终点,那么该list再加上vertex所表示的顶点本身,就可以表示与起点邻接的各个点了(称之为这个 起点的邻接表)。这样的边的特点是:边的所有的起始点都相同。
但是为了表示带权的边,因此,新增加weight属性,并用类edge来封装,这样不管是带权的边还是不带权的边都可以用同一个edge类来表示。不带权的边将weight赋值为0即可。
再分析顶点表:
定义接口vertexinterface<t>表示顶点的接口,所有的顶点都需要实现这个接口,该接口中定义了顶点的基本操作,如:判断顶点是否有邻接点,将顶点与另一个顶点连接起来...。其次,顶点表中的每个顶点有两个域,一个是标识域:v0,v1,v2,v3 。一个是指针域,指针域指向一个"单链表"。综上,设计一个类vertex.java 用来表示顶点,其数据域如下:
class vertex<t> implements vertexinterface<t>, java.io.serializable { private t label;//标识标点,可以用不同类型来标识顶点如string,integer.... private list<edge> edgelist;//到该顶点邻接点的边,实际以java.util.linkedlist存储 private boolean visited;//标识顶点是否已访问 private vertexinterface<t> previousvertex;//该顶点的前驱顶点 private double cost;//顶点的权值,与边的权值要区别开来
现在一一解释vertex类中定义的各个属性:
label : 用来标识顶点,如图中的 v0,v1,v2,v3,在实际代码中,v0...v3 以字符串的形式表示,就可以用来标识不同的顶点了。
因此,需要在vertex类中添加获得顶点标识的方法---getlabel()
public t getlabel() { return label; }
edgelist : 存放与该顶点关联的边。从上面edge.java中可以看到,edge的实质是“顶点”,因为,edge类除去wight属性,就只剩表示顶点的vertex属性了。借助edgelist,当给定一个顶点时,就可以访问该顶点的所有邻接点。因此,vertex.java中就需要实现根据edgelist中存放的边来遍历 某条边的终点(也即相应顶点的各个邻接点) 的迭代器了。
public iterator<vertexinterface<t>> getneighborinterator() { return new neighboriterator(); }
迭代器的实现如下:
/**task: 遍历该顶点邻接点的迭代器--为 getneighborinterator()方法 提供迭代器 * 由于顶点的邻接点以边的形式存储在java.util.list中,因此借助list的迭代器来实现 * 由于顶点的邻接点由edge类封装起来了--见edge.java的定义的第一个属性 * 因此,首先获得遍历edge对象的迭代器,再根据获得的edge对象解析出邻接点对象 */ private class neighboriterator implements iterator<vertexinterface<t>>{ iterator<edge> edgesiterator; private neighboriterator() { edgesiterator = edgelist.iterator();//获得遍历edgeslist 的迭代器 } @override public boolean hasnext() { return edgesiterator.hasnext(); } @override public vertexinterface<t> next() { vertexinterface<t> nextneighbor = null; if(edgesiterator.hasnext()){ edge edgetonextneighbor = edgesiterator.next();//linkedlist中存储的是edge nextneighbor = edgetonextneighbor.getendvertex();//从edge对象中取出顶点 } else throw new nosuchelementexception(); return nextneighbor; } @override public void remove() { throw new unsupportedoperationexception(); } }
visited : 之所以给每个顶点设置一个用来标记它是否被访问的属性,是因为:实现一个数据结构,是要用它去完成某些功能的,如遍历、查找…… 而在图的遍历过程中,就需要标记某个顶点是否被访问了,因此:设置该属性以便实现这些功能。那么,也就需要定义获取顶点是否被访问的isvisited()方法了。
public boolean isvisited() { return visited; }
previousvertex 属性 ,在求图中某两个顶点之间的最短路径时,在从起始顶点遍历过程中,需要记录下遍历到某个顶点时的前驱顶点, previousvertex 属性就派上用场了。因此,需要有判断和获取顶点的前驱顶点的方法:
public boolean haspredecessor() {//判断顶点是否有前驱顶点 return this.previousvertex != null; } public vertexinterface<t> getpredecessor() {//获得前驱顶点 return this.previousvertex; }
cost 属性:用来表示顶点的权值。注意,顶点的权值与边的权值是不同的。比如求无权图(默认是边不带权值)的最短路径时,如何求出顶点a到顶点b的最短的路径?由定义,该最短路径其实就是a走到b经历的最少边数目。因此,就可以用 cost 属性来记录a到b之间的距离是多少了。比如说,a 先走到 c 再走到b;初始时,a的 cost = 0,由于 a 是 c 的前驱,a到b需要经历c,c 的 cost 就是 c.previousvertex.cost + 1,直至 b,就可以求出 a 到 b 的最短路径了。详细算法及实现将会在第二篇博客中给出。
因此,针对 cost 属性,vertex.java需要实现的方法如下:
public void setcost(double newcost) { cost = newcost; } public double getcost() { return cost; }
3,总结:
从上可以看出,设计一个数据结构时,该数据结构需要包含哪些属性不是随意的,而是先确定该数据结构需要完成哪些功能(如,图的dfs、bfs、拓扑排序、最短路径),这些功能的实现需要借助哪些属性(如,求最短路径需要记录每个顶点的前驱顶点,就需要 previousvertex)。然后,去定义这些属性以及关于该属性的基本操作。设计一个合适的数据结构,当借助该数据结构来实现算法时,可以有效地降低算法的实现难度和复杂度!
vertex.java的完整代码如下:
package graph; import java.util.iterator; import java.util.linkedlist; import java.util.list; import java.util.nosuchelementexception; class vertex<t> implements vertexinterface<t>, java.io.serializable { private t label;//标识标点,可以用不同类型来标识顶点如string,integer.... private list<edge> edgelist;//到该顶点邻接点的边,实际以java.util.linkedlist存储 private boolean visited;//标识顶点是否已访问 private vertexinterface<t> previousvertex;//该顶点的前驱顶点 private double cost;//顶点的权值,与边的权值要区别开来 public vertex(t vertexlabel){ label = vertexlabel; edgelist = new linkedlist<edge>();//是vertex的属性,说明每个顶点都有一个edgelist用来存储所有与该顶点关系的边 visited = false; previousvertex = null; cost = 0; } /** *task: 这里用了一个单独的类来表示边,主要是考虑到带权值的边 *可以看出,edge类封装了一个顶点和一个double类型变量 *若不需要考虑权值,可以不需要单独创建一个edge类来表示边,只需要一个保存顶点的列表即可 * @author hapjin */ protected class edge implements java.io.serializable { private vertexinterface<t> vertex;// 终点 private double weight;//权值 //vertex 类本身就代表顶点对象,因此在这里只需提供 endvertex,就可以表示一条边了 protected edge(vertexinterface<t> endvertex, double edgeweight){ vertex = endvertex; weight = edgeweight; } protected vertexinterface<t> getendvertex(){ return vertex; } protected double getweight(){ return weight; } } /**task: 遍历该顶点邻接点的迭代器--为 getneighborinterator()方法 提供迭代器 * 由于顶点的邻接点以边的形式存储在java.util.list中,因此借助list的迭代器来实现 * 由于顶点的邻接点由edge类封装起来了--见edge.java的定义的第一个属性 * 因此,首先获得遍历edge对象的迭代器,再根据获得的edge对象解析出邻接点对象 */ private class neighboriterator implements iterator<vertexinterface<t>>{ iterator<edge> edgesiterator; private neighboriterator() { edgesiterator = edgelist.iterator();//获得遍历edgeslist 的迭代器 } @override public boolean hasnext() { return edgesiterator.hasnext(); } @override public vertexinterface<t> next() { vertexinterface<t> nextneighbor = null; if(edgesiterator.hasnext()){ edge edgetonextneighbor = edgesiterator.next();//linkedlist中存储的是edge nextneighbor = edgetonextneighbor.getendvertex();//从edge对象中取出顶点 } else throw new nosuchelementexception(); return nextneighbor; } @override public void remove() { throw new unsupportedoperationexception(); } } /**task: 生成一个遍历该顶点所有邻接边的权值的迭代器 * 权值是edge类的属性,因此先获得一个遍历edge对象的迭代器,取得edge对象,再获得权值 * @author hapjin * * @param <double> 权值的类型 */ private class weightiterator implements iterator{//这里不知道为什么,用泛型报编译错误??? private iterator<edge> edgesiterator; private weightiterator(){ edgesiterator = edgelist.iterator(); } @override public boolean hasnext() { return edgesiterator.hasnext(); } @override public object next() { double result; if(edgesiterator.hasnext()){ edge edge = edgesiterator.next(); result = edge.getweight(); } else throw new nosuchelementexception(); return (object)result;//从迭代器中取得结果时,需要强制转换成double } @override public void remove() { throw new unsupportedoperationexception(); } } @override public t getlabel() { return label; } @override public void visit() { this.visited = true; } @override public void unvisit() { this.visited = false; } @override public boolean isvisited() { return visited; } @override public boolean connect(vertexinterface<t> endvertex, double edgeweight) { // 将"边"(边的实质是顶点)插入顶点的邻接表 boolean result = false; if(!this.equals(endvertex)){//顶点互不相同 iterator<vertexinterface<t>> neighbors = this.getneighborinterator(); boolean duplicateedge = false; while(!duplicateedge && neighbors.hasnext()){//保证不添加重复的边 vertexinterface<t> nextneighbor = neighbors.next(); if(endvertex.equals(nextneighbor)){ duplicateedge = true; break; } }//end while if(!duplicateedge){ edgelist.add(new edge(endvertex, edgeweight));//添加一条新边 result = true; }//end if }//end if return result; } @override public boolean connect(vertexinterface<t> endvertex) { return connect(endvertex, 0); } @override public iterator<vertexinterface<t>> getneighborinterator() { return new neighboriterator(); } @override public iterator getweightiterator() { return new weightiterator(); } @override public boolean hasneighbor() { return !(edgelist.isempty());//邻接点实质是存储是list中 } @override public vertexinterface<t> getunvisitedneighbor() { vertexinterface<t> result = null; iterator<vertexinterface<t>> neighbors = getneighborinterator(); while(neighbors.hasnext() && result == null){//获得该顶点的第一个未被访问的邻接点 vertexinterface<t> nextneighbor = neighbors.next(); if(!nextneighbor.isvisited()) result = nextneighbor; } return result; } @override public void setpredecessor(vertexinterface<t> predecessor) { this.previousvertex = predecessor; } @override public vertexinterface<t> getpredecessor() { return this.previousvertex; } @override public boolean haspredecessor() { return this.previousvertex != null; } @override public void setcost(double newcost) { cost = newcost; } @override public double getcost() { return cost; } //判断两个顶点是否相同 public boolean equals(object other){ boolean result; if((other == null) || (getclass() != other.getclass())) result = false; else { vertex<t> othervertex = (vertex<t>)other; result = label.equals(othervertex.label);//节点是否相同最终还是由标识 节点类型的类的equals() 决定 } return result; } }
以上所述是小编给大家介绍的java数据结构之图(动力节点java学院整理),希望对大家有所帮助