Java數(shù)據(jù)結(jié)構(gòu)之圖(動(dòng)力節(jié)點(diǎn)Java學(xué)院整理)
1，摘要：
本文章主要講解學(xué)習(xí)如何使用JAVA語(yǔ)言以鄰接表的方式實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)---圖（Graph）。從數(shù)據(jù)的表示方法來(lái)說(shuō)，有二種表示圖的方式：一種是鄰接矩陣，其實(shí)是一個(gè)二維數(shù)組；一種是鄰接表，其實(shí)是一個(gè)頂點(diǎn)表，每個(gè)頂點(diǎn)又擁有一個(gè)邊列表。下圖是圖的鄰接表表示。
從圖中可以看出，圖的實(shí)現(xiàn)需要能夠表示頂點(diǎn)表，能夠表示邊表。鄰接表指是的哪部分呢？每個(gè)頂點(diǎn)都有一個(gè)鄰接表，一個(gè)指定頂點(diǎn)的鄰接表中，起始頂點(diǎn)表示邊的起點(diǎn)，其他頂點(diǎn)表示邊的終點(diǎn)。這樣，就可以用鄰接表來(lái)實(shí)現(xiàn)邊的表示了。如頂點(diǎn)V0的鄰接表如下：
與V0關(guān)聯(lián)的邊有三條，因?yàn)閂0的鄰接表中有三個(gè)頂點(diǎn)(不考慮V0)。
2，具體分析
先來(lái)分析邊表：
在圖中如何來(lái)表示一條邊？很簡(jiǎn)單，就是：起始頂點(diǎn)指向結(jié)束頂點(diǎn)、就是頂點(diǎn)對(duì)<startVertex, endVertex>。在這里，為了考慮邊帶有權(quán)值的情況，單獨(dú)設(shè)計(jì)一個(gè)類Edge.java，作為Vertex.java的內(nèi)部類，Edge.java如下：
protected class Edge implements java.io.Serializable {
private VertexInterface<T> vertex;// 終點(diǎn)
private double weight;//權(quán)值
Edge類中只有兩個(gè)屬性，vertex 用來(lái)表示頂點(diǎn)，該頂點(diǎn)是邊的終點(diǎn)。weight 表示邊的權(quán)值。若不考慮帶權(quán)的情況，就不需要weight屬性，那么可以直接定義一個(gè)頂點(diǎn)列表 來(lái)存放 終點(diǎn) 就可以表示邊了。這是因?yàn)椋哼@些屬性是定義在Vertex.java中，而Vertex本身就表示頂點(diǎn)，如果在Vertex內(nèi)部定義一個(gè)List存放終點(diǎn)，那么該List再加上Vertex所表示的頂點(diǎn)本身，就可以表示與起點(diǎn)鄰接的各個(gè)點(diǎn)了（稱之為這個(gè) 起點(diǎn)的鄰接表）。這樣的邊的特點(diǎn)是：邊的所有的起始點(diǎn)都相同。
但是為了表示帶權(quán)的邊，因此，新增加weight屬性，并用類Edge來(lái)封裝，這樣不管是帶權(quán)的邊還是不帶權(quán)的邊都可以用同一個(gè)Edge類來(lái)表示。不帶權(quán)的邊將weight賦值為0即可。
再分析頂點(diǎn)表：
定義接口VertexInterface<T>表示頂點(diǎn)的接口，所有的頂點(diǎn)都需要實(shí)現(xiàn)這個(gè)接口，該接口中定義了頂點(diǎn)的基本操作，如：判斷頂點(diǎn)是否有鄰接點(diǎn)，將頂點(diǎn)與另一個(gè)頂點(diǎn)連接起來(lái)...。其次，頂點(diǎn)表中的每個(gè)頂點(diǎn)有兩個(gè)域，一個(gè)是標(biāo)識(shí)域：V0,V1,V2,V3 。一個(gè)是指針域，指針域指向一個(gè)"單鏈表"。綜上，設(shè)計(jì)一個(gè)類Vertex.java 用來(lái)表示頂點(diǎn)，其數(shù)據(jù)域如下：
class Vertex<T> implements VertexInterface<T>, java.io.Serializable {
private T label;//標(biāo)識(shí)標(biāo)點(diǎn),可以用不同類型來(lái)標(biāo)識(shí)頂點(diǎn)如String,Integer....
private List<Edge> edgeList;//到該頂點(diǎn)鄰接點(diǎn)的邊,實(shí)際以java.util.LinkedList存儲(chǔ)
private boolean visited;//標(biāo)識(shí)頂點(diǎn)是否已訪問(wèn)
private VertexInterface<T> previousVertex;//該頂點(diǎn)的前驅(qū)頂點(diǎn)
private double cost;//頂點(diǎn)的權(quán)值,與邊的權(quán)值要區(qū)別開(kāi)來(lái)
現(xiàn)在一一解釋Vertex類中定義的各個(gè)屬性：
label : 用來(lái)標(biāo)識(shí)頂點(diǎn)，如圖中的 V0,V1,V2,V3，在實(shí)際代碼中，V0...V3 以字符串的形式表示，就可以用來(lái)標(biāo)識(shí)不同的頂點(diǎn)了。
因此，需要在Vertex類中添加獲得頂點(diǎn)標(biāo)識(shí)的方法---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)給定一個(gè)頂點(diǎn)時(shí)，就可以訪問(wèn)該頂點(diǎn)的所有鄰接點(diǎn)。因此，Vertex.java中就需要實(shí)現(xiàn)根據(jù)edgeList中存放的邊來(lái)遍歷 某條邊的終點(diǎn)(也即相應(yīng)頂點(diǎn)的各個(gè)鄰接點(diǎn)) 的迭代器了。
public Iterator<VertexInterface<T>> getNeighborInterator() {
return new NeighborIterator();
}
迭代器的實(shí)現(xiàn)如下：
/**Task: 遍歷該頂點(diǎn)鄰接點(diǎn)的迭代器--為 getNeighborInterator()方法 提供迭代器
* 由于頂點(diǎn)的鄰接點(diǎn)以邊的形式存儲(chǔ)在java.util.List中,因此借助List的迭代器來(lái)實(shí)現(xiàn)
* 由于頂點(diǎn)的鄰接點(diǎn)由Edge類封裝起來(lái)了--見(jiàn)Edge.java的定義的第一個(gè)屬性
* 因此，首先獲得遍歷Edge對(duì)象的迭代器,再根據(jù)獲得的Edge對(duì)象解析出鄰接點(diǎn)對(duì)象
*/
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中存儲(chǔ)的是Edge
nextNeighbor = edgeToNextNeighbor.getEndVertex();//從Edge對(duì)象中取出頂點(diǎn)
}
else
throw new NoSuchElementException();
return nextNeighbor;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
visited : 之所以給每個(gè)頂點(diǎn)設(shè)置一個(gè)用來(lái)標(biāo)記它是否被訪問(wèn)的屬性，是因?yàn)椋簩?shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)，是要用它去完成某些功能的，如遍歷、查找…… 而在圖的遍歷過(guò)程中，就需要標(biāo)記某個(gè)頂點(diǎn)是否被訪問(wèn)了，因此：設(shè)置該屬性以便實(shí)現(xiàn)這些功能。那么，也就需要定義獲取頂點(diǎn)是否被訪問(wèn)的isVisited()方法了。
public boolean isVisited() {
return visited;
}
previousVertex 屬性 ，在求圖中某兩個(gè)頂點(diǎn)之間的最短路徑時(shí)，在從起始頂點(diǎn)遍歷過(guò)程中，需要記錄下遍歷到某個(gè)頂點(diǎn)時(shí)的前驅(qū)頂點(diǎn)， previousVertex 屬性就派上用場(chǎng)了。因此，需要有判斷和獲取頂點(diǎn)的前驅(qū)頂點(diǎn)的方法：
public boolean hasPredecessor() {//判斷頂點(diǎn)是否有前驅(qū)頂點(diǎn)
return this.previousVertex != null;
}
public VertexInterface<T> getPredecessor() {//獲得前驅(qū)頂點(diǎn)
return this.previousVertex;
}
cost 屬性：用來(lái)表示頂點(diǎn)的權(quán)值。注意，頂點(diǎn)的權(quán)值與邊的權(quán)值是不同的。比如求無(wú)權(quán)圖（默認(rèn)是邊不帶權(quán)值）的最短路徑時(shí)，如何求出頂點(diǎn)A到頂點(diǎn)B的最短的路徑？由定義，該最短路徑其實(shí)就是A走到B經(jīng)歷的最少邊數(shù)目。因此，就可以用 cost 屬性來(lái)記錄A到B之間的距離是多少了。比如說(shuō)，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)將會(huì)在第二篇博客中給出。
因此，針對(duì) cost 屬性，Vertex.java需要實(shí)現(xiàn)的方法如下：
public void setCost(double newCost) {
cost = newCost;
}
public double getCost() {
return cost;
}
3，總結(jié)：
從上可以看出，設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)時(shí)，該數(shù)據(jù)結(jié)構(gòu)需要包含哪些屬性不是隨意的，而是先確定該數(shù)據(jù)結(jié)構(gòu)需要完成哪些功能（如，圖的DFS、BFS、拓?fù)渑判颉⒆疃搪窂剑?，這些功能的實(shí)現(xiàn)需要借助哪些屬性(如，求最短路徑需要記錄每個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)，就需要 previousVertex)。然后，去定義這些屬性以及關(guān)于該屬性的基本操作。設(shè)計(jì)一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，當(dāng)借助該數(shù)據(jù)結(jié)構(gòu)來(lái)實(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<T> implements VertexInterface<T>, java.io.Serializable {
private T label;//標(biāo)識(shí)標(biāo)點(diǎn),可以用不同類型來(lái)標(biāo)識(shí)頂點(diǎn)如String,Integer....
private List<Edge> edgeList;//到該頂點(diǎn)鄰接點(diǎn)的邊,實(shí)際以java.util.LinkedList存儲(chǔ)
private boolean visited;//標(biāo)識(shí)頂點(diǎn)是否已訪問(wèn)
private VertexInterface<T> previousVertex;//該頂點(diǎn)的前驅(qū)頂點(diǎn)
private double cost;//頂點(diǎn)的權(quán)值,與邊的權(quán)值要區(qū)別開(kāi)來(lái)
public Vertex(T vertexLabel){
label = vertexLabel;
edgeList = new LinkedList<Edge>();//是Vertex的屬性,說(shuō)明每個(gè)頂點(diǎn)都有一個(gè)edgeList用來(lái)存儲(chǔ)所有與該頂點(diǎn)關(guān)系的邊
visited = false;
previousVertex = null;
cost = 0;
}
/**
*Task: 這里用了一個(gè)單獨(dú)的類來(lái)表示邊,主要是考慮到帶權(quán)值的邊
*可以看出,Edge類封裝了一個(gè)頂點(diǎn)和一個(gè)double類型變量
*若不需要考慮權(quán)值,可以不需要單獨(dú)創(chuàng)建一個(gè)Edge類來(lái)表示邊,只需要一個(gè)保存頂點(diǎn)的列表即可
* @author hapjin
*/
protected class Edge implements java.io.Serializable {
private VertexInterface<T> vertex;// 終點(diǎn)
private double weight;//權(quán)值
//Vertex 類本身就代表頂點(diǎn)對(duì)象,因此在這里只需提供 endVertex，就可以表示一條邊了
protected Edge(VertexInterface<T> endVertex, double edgeWeight){
vertex = endVertex;
weight = edgeWeight;
}
protected VertexInterface<T> getEndVertex(){
return vertex;
}
protected double getWeight(){
return weight;
}
}
/**Task: 遍歷該頂點(diǎn)鄰接點(diǎn)的迭代器--為 getNeighborInterator()方法 提供迭代器
* 由于頂點(diǎn)的鄰接點(diǎn)以邊的形式存儲(chǔ)在java.util.List中,因此借助List的迭代器來(lái)實(shí)現(xiàn)
* 由于頂點(diǎn)的鄰接點(diǎn)由Edge類封裝起來(lái)了--見(jiàn)Edge.java的定義的第一個(gè)屬性
* 因此，首先獲得遍歷Edge對(duì)象的迭代器,再根據(jù)獲得的Edge對(duì)象解析出鄰接點(diǎn)對(duì)象
*/
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中存儲(chǔ)的是Edge
nextNeighbor = edgeToNextNeighbor.getEndVertex();//從Edge對(duì)象中取出頂點(diǎn)
}
else
throw new NoSuchElementException();
return nextNeighbor;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
/**Task: 生成一個(gè)遍歷該頂點(diǎn)所有鄰接邊的權(quán)值的迭代器
* 權(quán)值是Edge類的屬性,因此先獲得一個(gè)遍歷Edge對(duì)象的迭代器,取得Edge對(duì)象,再獲得權(quán)值
* @author hapjin
*
* @param <Double> 權(quán)值的類型
*/
private class WeightIterator implements Iterator{//這里不知道為什么,用泛型報(bào)編譯錯(cuò)誤???
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;//從迭代器中取得結(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<T> endVertex, double edgeWeight) {
// 將"邊"(邊的實(shí)質(zhì)是頂點(diǎn))插入頂點(diǎn)的鄰接表
boolean result = false;
if(!this.equals(endVertex)){//頂點(diǎn)互不相同
Iterator<VertexInterface<T>> neighbors = this.getNeighborInterator();
boolean duplicateEdge = false;
while(!duplicateEdge && neighbors.hasNext()){//保證不添加重復(fù)的邊
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());//鄰接點(diǎn)實(shí)質(zhì)是存儲(chǔ)是List中
}
@Override
public VertexInterface<T> getUnvisitedNeighbor() {
VertexInterface<T> result = null;
Iterator<VertexInterface<T>> neighbors = getNeighborInterator();
while(neighbors.hasNext() && result == null){//獲得該頂點(diǎn)的第一個(gè)未被訪問(wèn)的鄰接點(diǎn)
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;
}
//判斷兩個(gè)頂點(diǎn)是否相同
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);//節(jié)點(diǎn)是否相同最終還是由標(biāo)識(shí) 節(jié)點(diǎn)類型的類的equals() 決定
}
return result;
}
}
以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)之圖(動(dòng)力節(jié)點(diǎn)Java學(xué)院整理)，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
相關(guān)文章
在日常開(kāi)發(fā)中,我們經(jīng)常需要處理日期和時(shí)間,所以這篇文章小編為大家總結(jié)了下?Java?中日期與時(shí)間的基本概念與一些常用的用法,希望對(duì)大家有所幫助2023-09-09
Java class文件格式總結(jié)_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
這篇文章主要介紹了Java class文件格式總結(jié)的相關(guān)資料，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的的朋友參考下吧2017-06-06
javaweb圖書商城設(shè)計(jì)之分類模塊(2)
這篇文章主要為大家詳細(xì)介紹了javaweb圖書商城設(shè)計(jì)之分類模塊的相關(guān)資料,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-11-11
java報(bào)錯(cuò)Cause: java.sql.SQLException問(wèn)題解決
本文主要介紹了java報(bào)錯(cuò)Cause: java.sql.SQLException問(wèn)題解決,對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
JAVA用遞歸實(shí)現(xiàn)全排列算法的示例代碼
這篇文章主要介紹了JAVA用遞歸實(shí)現(xiàn)全排列算法的相關(guān)資料，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
面試時(shí)必問(wèn)的JVM運(yùn)行時(shí)數(shù)據(jù)區(qū)詳解
這篇文章主要介紹了JVM運(yùn)行時(shí)數(shù)據(jù)區(qū)原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2021-08-08
SpringBoot整合jasypt實(shí)現(xiàn)敏感信息的加密詳解
一般公司的核心業(yè)務(wù)代碼中，都會(huì)存在與數(shù)據(jù)庫(kù)、第三方通信的secret key等敏感信息，如果以明文的方式存儲(chǔ)，一旦泄露，那將會(huì)給公司帶來(lái)巨大的損失。本篇文章通過(guò)講解：Springboot集成Jasypt對(duì)項(xiàng)目敏感信息進(jìn)行加密，提高系統(tǒng)的安全性2022-09-09
java中線程的基本方法的熟練使用是精通多線程編程的必經(jīng)之路，線程相關(guān)的基本方法有wait，notify，notifyAll，sleep，join，yield等，本文淺要的介紹一下它們的使用方式2021-06-06
MyBatis使用注解開(kāi)發(fā)實(shí)現(xiàn)過(guò)程詳解
這篇文章主要介紹了MyBatis使用注解開(kāi)發(fā)實(shí)現(xiàn)過(guò)程詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
在VSCode里使用Jupyter?Notebook調(diào)試Java代碼的詳細(xì)過(guò)程
Jupyter Notebook是以網(wǎng)頁(yè)的形式打開(kāi)，可以在網(wǎng)頁(yè)頁(yè)面中直接編寫代碼和運(yùn)行代碼，代碼的運(yùn)行結(jié)果也會(huì)直接在代碼塊下顯示的程序，這篇文章主要介紹了在VSCode里使用Jupyter?Notebook，調(diào)試Java代碼,需要的朋友可以參考下2022-07-07