Java数据结构之图数据结构之图(动力节点动力节点Java学院整理学院整理)
本文章主要讲解学习如何使用JAVA语言以邻接表的方式实现了数据结构---图(Graph)。对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;//顶点的权值,与边的权值要区别开来