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学院整理)，希望对大家有所帮助