深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖

本篇文章為大家展示了深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

個舊網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)公司等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。創(chuàng)新互聯(lián)從2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

1，摘要：

從數(shù)據(jù)的表示方法來說，有二種表示圖的方式：一種是鄰接矩陣，其實(shí)是一個二維數(shù)組；一種是鄰接表，其實(shí)是一個頂點(diǎn)表，每個頂點(diǎn)又擁有一個邊列表。下圖是圖的鄰接表表示。

從圖中可以看出，圖的實(shí)現(xiàn)需要能夠表示頂點(diǎn)表，能夠表示邊表。鄰接表指是的哪部分呢？每個頂點(diǎn)都有一個鄰接表，一個指定頂點(diǎn)的鄰接表中，起始頂點(diǎn)表示邊的起點(diǎn)，其他頂點(diǎn)表示邊的終點(diǎn)。這樣，就可以用鄰接表來實(shí)現(xiàn)邊的表示了。如頂點(diǎn)V0的鄰接表如下：

深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖

與V0關(guān)聯(lián)的邊有三條，因?yàn)閂0的鄰接表中有三個頂點(diǎn)(不考慮V0)。

2，具體分析

先來分析邊表：

在圖中如何來表示一條邊？很簡單，就是：起始頂點(diǎn)指向結(jié)束頂點(diǎn)、就是頂點(diǎn)對。在這里，為了考慮邊帶有權(quán)值的情況，單獨(dú)設(shè)計(jì)一個類Edge.java，作為Vertex.java的內(nèi)部類，Edge.java如下：

 protected class Edge implements java.io.Serializable {
     private VertexInterface vertex;// 終點(diǎn)
    private double weight;//權(quán)值

Edge類中只有兩個屬性，vertex 用來表示頂點(diǎn)，該頂點(diǎn)是邊的終點(diǎn)。weight 表示邊的權(quán)值。若不考慮帶權(quán)的情況，就不需要weight屬性，那么可以直接定義一個頂點(diǎn)列表來存放終點(diǎn) 就可以表示邊了。這是因?yàn)椋哼@些屬性是定義在Vertex.java中，而Vertex本身就表示頂點(diǎn)，如果在Vertex內(nèi)部定義一個List存放終點(diǎn)，那么該List再加上Vertex所表示的頂點(diǎn)本身，就可以表示與起點(diǎn)鄰接的各個點(diǎn)了（稱之為這個起點(diǎn)的鄰接表）。這樣的邊的特點(diǎn)是：邊的所有的起始點(diǎn)都相同。

但是為了表示帶權(quán)的邊，因此，新增加weight屬性，并用類Edge來封裝，這樣不管是帶權(quán)的邊還是不帶權(quán)的邊都可以用同一個Edge類來表示。不帶權(quán)的邊將weight賦值為0即可。

再分析頂點(diǎn)表：

定義接口VertexInterface表示頂點(diǎn)的接口，所有的頂點(diǎn)都需要實(shí)現(xiàn)這個接口，該接口中定義了頂點(diǎn)的基本操作，如：判斷頂點(diǎn)是否有鄰接點(diǎn)，將頂點(diǎn)與另一個頂點(diǎn)連接起來...。其次，頂點(diǎn)表中的每個頂點(diǎn)有兩個域，一個是標(biāo)識域：V0,V1,V2,V3 。一個是指針域，指針域指向一個"單鏈表"。綜上，設(shè)計(jì)一個類Vertex.java 用來表示頂點(diǎn)，其數(shù)據(jù)域如下：

class Vertex implements VertexInterface, java.io.Serializable {
  private T label;//標(biāo)識標(biāo)點(diǎn),可以用不同類型來標(biāo)識頂點(diǎn)如String,Integer....
  private List edgeList;//到該頂點(diǎn)鄰接點(diǎn)的邊,實(shí)際以java.util.LinkedList存儲
  private boolean visited;//標(biāo)識頂點(diǎn)是否已訪問
  private VertexInterface previousVertex;//該頂點(diǎn)的前驅(qū)頂點(diǎn)
  private double cost;//頂點(diǎn)的權(quán)值,與邊的權(quán)值要區(qū)別開來

現(xiàn)在一一解釋Vertex類中定義的各個屬性：

label : 用來標(biāo)識頂點(diǎn)，如圖中的 V0,V1,V2,V3，在實(shí)際代碼中，V0...V3 以字符串的形式表示，就可以用來標(biāo)識不同的頂點(diǎn)了。

因此，需要在Vertex類中添加獲得頂點(diǎn)標(biāo)識的方法---getLabel()

   public T getLabel() {
     return label;
   }

edgeList : 存放與該頂點(diǎn)關(guān)聯(lián)的邊。從上面Edge.java中可以看到，Edge的實(shí)質(zhì)是“頂點(diǎn)”，因?yàn)?，Edge類除去wight屬性，就只剩表示頂點(diǎn)的vertex屬性了。借助edgeList，當(dāng)給定一個頂點(diǎn)時(shí)，就可以訪問該頂點(diǎn)的所有鄰接點(diǎn)。因此，Vertex.java中就需要實(shí)現(xiàn)根據(jù)edgeList中存放的邊來遍歷某條邊的終點(diǎn)(也即相應(yīng)頂點(diǎn)的各個鄰接點(diǎn)) 的迭代器了。

 public Iterator> getNeighborInterator() {
     return new NeighborIterator();
   }

迭代器的實(shí)現(xiàn)如下：

/**Task: 遍歷該頂點(diǎn)鄰接點(diǎn)的迭代器--為 getNeighborInterator()方法 提供迭代器
   * 由于頂點(diǎn)的鄰接點(diǎn)以邊的形式存儲在java.util.List中,因此借助List的迭代器來實(shí)現(xiàn)
   * 由于頂點(diǎn)的鄰接點(diǎn)由Edge類封裝起來了--見Edge.java的定義的第一個屬性
   * 因此，首先獲得遍歷Edge對象的迭代器,再根據(jù)獲得的Edge對象解析出鄰接點(diǎn)對象
   */
  private class NeighborIterator implements Iterator>{
    Iterator edgesIterator;
    private NeighborIterator() {
      edgesIterator = edgeList.iterator();//獲得遍歷edgesList 的迭代器
    }
    @Override
    public boolean hasNext() {
      return edgesIterator.hasNext();
    }
    @Override
    public VertexInterface next() {
      VertexInterface nextNeighbor = null;
      if(edgesIterator.hasNext()){
        Edge edgeToNextNeighbor = edgesIterator.next();//LinkedList中存儲的是Edge
        nextNeighbor = edgeToNextNeighbor.getEndVertex();//從Edge對象中取出頂點(diǎn)
      }
      else
        throw new NoSuchElementException();
      return nextNeighbor;
    }
    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }

visited : 之所以給每個頂點(diǎn)設(shè)置一個用來標(biāo)記它是否被訪問的屬性，是因?yàn)椋簩?shí)現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)，是要用它去完成某些功能的，如遍歷、查找…… 而在圖的遍歷過程中，就需要標(biāo)記某個頂點(diǎn)是否被訪問了，因此：設(shè)置該屬性以便實(shí)現(xiàn)這些功能。那么，也就需要定義獲取頂點(diǎn)是否被訪問的isVisited()方法了。

  public boolean isVisited() {
    return visited;
   }

previousVertex 屬性，在求圖中某兩個頂點(diǎn)之間的最短路徑時(shí)，在從起始頂點(diǎn)遍歷過程中，需要記錄下遍歷到某個頂點(diǎn)時(shí)的前驅(qū)頂點(diǎn)， previousVertex 屬性就派上用場了。因此，需要有判斷和獲取頂點(diǎn)的前驅(qū)頂點(diǎn)的方法：

   public boolean hasPredecessor() {//判斷頂點(diǎn)是否有前驅(qū)頂點(diǎn)
     return this.previousVertex != null;
   }
  public VertexInterface getPredecessor() {//獲得前驅(qū)頂點(diǎn)
     return this.previousVertex;
  }

cost 屬性：用來表示頂點(diǎn)的權(quán)值。注意，頂點(diǎn)的權(quán)值與邊的權(quán)值是不同的。比如求無權(quán)圖（默認(rèn)是邊不帶權(quán)值）的最短路徑時(shí)，如何求出頂點(diǎn)A到頂點(diǎn)B的最短的路徑？由定義，該最短路徑其實(shí)就是A走到B經(jīng)歷的最少邊數(shù)目。因此，就可以用 cost 屬性來記錄A到B之間的距離是多少了。比如說，A 先走到 C 再走到B；初始時(shí)，A的 cost = 0，由于 A 是 C 的前驅(qū)，A到B需要經(jīng)歷C，C 的 cost 就是 c.previousVertex.cost + 1，直至 B，就可以求出 A 到 B 的最短路徑了。詳細(xì)算法及實(shí)現(xiàn)將會在第二篇博客中給出。

因此，針對 cost 屬性，Vertex.java需要實(shí)現(xiàn)的方法如下：

 public void setCost(double newCost) {
     cost = newCost;
   }
 public double getCost() {
    return cost;
  }

3，總結(jié)：

從上可以看出，設(shè)計(jì)一個數(shù)據(jù)結(jié)構(gòu)時(shí)，該數(shù)據(jù)結(jié)構(gòu)需要包含哪些屬性不是隨意的，而是先確定該數(shù)據(jù)結(jié)構(gòu)需要完成哪些功能（如，圖的DFS、BFS、拓?fù)渑判?、最短路徑），這些功能的實(shí)現(xiàn)需要借助哪些屬性(如，求最短路徑需要記錄每個頂點(diǎn)的前驅(qū)頂點(diǎn)，就需要 previousVertex)。然后，去定義這些屬性以及關(guān)于該屬性的基本操作。設(shè)計(jì)一個合適的數(shù)據(jù)結(jié)構(gòu)，當(dāng)借助該數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)算法時(shí)，可以有效地降低算法的實(shí)現(xiàn)難度和復(fù)雜度！

Vertex.java的完整代碼如下：

package graph;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
class Vertex implements VertexInterface, java.io.Serializable {
  private T label;//標(biāo)識標(biāo)點(diǎn),可以用不同類型來標(biāo)識頂點(diǎn)如String,Integer....
  private List edgeList;//到該頂點(diǎn)鄰接點(diǎn)的邊,實(shí)際以java.util.LinkedList存儲
  private boolean visited;//標(biāo)識頂點(diǎn)是否已訪問
  private VertexInterface previousVertex;//該頂點(diǎn)的前驅(qū)頂點(diǎn)
  private double cost;//頂點(diǎn)的權(quán)值,與邊的權(quán)值要區(qū)別開來
  public Vertex(T vertexLabel){
    label = vertexLabel;
    edgeList = new LinkedList();//是Vertex的屬性,說明每個頂點(diǎn)都有一個edgeList用來存儲所有與該頂點(diǎn)關(guān)系的邊
    visited = false;
    previousVertex = null;
    cost = 0;
  }
  /**
   *Task: 這里用了一個單獨(dú)的類來表示邊,主要是考慮到帶權(quán)值的邊
   *可以看出,Edge類封裝了一個頂點(diǎn)和一個double類型變量 
   *若不需要考慮權(quán)值,可以不需要單獨(dú)創(chuàng)建一個Edge類來表示邊,只需要一個保存頂點(diǎn)的列表即可
   * @author hapjin
   */
  protected class Edge implements java.io.Serializable {
    private VertexInterface vertex;// 終點(diǎn)
    private double weight;//權(quán)值
    //Vertex 類本身就代表頂點(diǎn)對象,因此在這里只需提供 endVertex，就可以表示一條邊了
    protected Edge(VertexInterface endVertex, double edgeWeight){
      vertex = endVertex;
      weight = edgeWeight;
    }
    protected VertexInterface getEndVertex(){
      return vertex;
    }
    protected double getWeight(){
      return weight;
    }
  }
  /**Task: 遍歷該頂點(diǎn)鄰接點(diǎn)的迭代器--為 getNeighborInterator()方法 提供迭代器
   * 由于頂點(diǎn)的鄰接點(diǎn)以邊的形式存儲在java.util.List中,因此借助List的迭代器來實(shí)現(xiàn)
   * 由于頂點(diǎn)的鄰接點(diǎn)由Edge類封裝起來了--見Edge.java的定義的第一個屬性
   * 因此，首先獲得遍歷Edge對象的迭代器,再根據(jù)獲得的Edge對象解析出鄰接點(diǎn)對象
   */
  private class NeighborIterator implements Iterator>{
    Iterator edgesIterator;
    private NeighborIterator() {
      edgesIterator = edgeList.iterator();//獲得遍歷edgesList 的迭代器
    }
    @Override
    public boolean hasNext() {
      return edgesIterator.hasNext();
    }
    @Override
    public VertexInterface next() {
      VertexInterface nextNeighbor = null;
      if(edgesIterator.hasNext()){
        Edge edgeToNextNeighbor = edgesIterator.next();//LinkedList中存儲的是Edge
        nextNeighbor = edgeToNextNeighbor.getEndVertex();//從Edge對象中取出頂點(diǎn)
      }
      else
        throw new NoSuchElementException();
      return nextNeighbor;
    }
    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }
  /**Task: 生成一個遍歷該頂點(diǎn)所有鄰接邊的權(quán)值的迭代器
   * 權(quán)值是Edge類的屬性,因此先獲得一個遍歷Edge對象的迭代器,取得Edge對象,再獲得權(quán)值
   * @author hapjin
   *
   * @param  權(quán)值的類型
   */
  private class WeightIterator implements Iterator{//這里不知道為什么,用泛型報(bào)編譯錯誤???
    private Iterator 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;//從迭代器中取得結(jié)果時(shí),需要強(qiáng)制轉(zhuǎn)換成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 endVertex, double edgeWeight) {
    // 將"邊"(邊的實(shí)質(zhì)是頂點(diǎn))插入頂點(diǎn)的鄰接表
    boolean result = false;
    if(!this.equals(endVertex)){//頂點(diǎn)互不相同
      Iterator> neighbors = this.getNeighborInterator();
      boolean duplicateEdge = false;
      while(!duplicateEdge && neighbors.hasNext()){//保證不添加重復(fù)的邊
        VertexInterface 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 endVertex) {
    return connect(endVertex, 0);
  }
  @Override
  public Iterator> getNeighborInterator() {
    return new NeighborIterator();
  }
  @Override
  public Iterator getWeightIterator() {
    return new WeightIterator();
  }
  @Override
  public boolean hasNeighbor() {
    return !(edgeList.isEmpty());//鄰接點(diǎn)實(shí)質(zhì)是存儲是List中
  }
  @Override
  public VertexInterface getUnvisitedNeighbor() {
    VertexInterface result = null;
    Iterator> neighbors = getNeighborInterator();
    while(neighbors.hasNext() && result == null){//獲得該頂點(diǎn)的第一個未被訪問的鄰接點(diǎn)
      VertexInterface nextNeighbor = neighbors.next();
      if(!nextNeighbor.isVisited())
        result = nextNeighbor;
    }
    return result;
  }
  @Override
  public void setPredecessor(VertexInterface predecessor) {
    this.previousVertex = predecessor;
  }
  @Override
  public VertexInterface 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;
  }
  //判斷兩個頂點(diǎn)是否相同
  public boolean equals(Object other){
    boolean result;
    if((other == null) || (getClass() != other.getClass()))
      result = false;
    else
    {
      Vertex otherVertex = (Vertex)other;
      result = label.equals(otherVertex.label);//節(jié)點(diǎn)是否相同最終還是由標(biāo)識 節(jié)點(diǎn)類型的類的equals() 決定
    }
    return result;
  }
}

上述內(nèi)容就是深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

文章題目：深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖
文章網(wǎng)址：http://m.jiaotiyi.com/article/psoiho.html

網(wǎng)站建設(shè)知識

深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖

其他資訊