本篇文章為大家展示了深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖,內(nèi)容簡(jiǎn)明扼要并且容易理解,絕對(duì)能使你眼前一亮,通過這篇文章的詳細(xì)介紹希望你能有所收獲。
個(gè)舊網(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)營(yíng)維護(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í)是一個(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)。這樣,就可以用鄰接表來實(shí)現(xiàn)邊的表示了。如頂點(diǎn)V0的鄰接表如下:
與V0關(guān)聯(lián)的邊有三條,因?yàn)閂0的鄰接表中有三個(gè)頂點(diǎn)(不考慮V0)。
2,具體分析
先來分析邊表:
在圖中如何來表示一條邊?很簡(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 用來表示頂點(diǎn),該頂點(diǎn)是邊的終點(diǎn)。weight 表示邊的權(quán)值。若不考慮帶權(quán)的情況,就不需要weight屬性,那么可以直接定義一個(gè)頂點(diǎn)列表 來存放 終點(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來封裝,這樣不管是帶權(quán)的邊還是不帶權(quán)的邊都可以用同一個(gè)Edge類來表示。不帶權(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)連接起來...。其次,頂點(diǎn)表中的每個(gè)頂點(diǎn)有兩個(gè)域,一個(gè)是標(biāo)識(shí)域:V0,V1,V2,V3 。一個(gè)是指針域,指針域指向一個(gè)"單鏈表"。綜上,設(shè)計(jì)一個(gè)類Vertex.java 用來表示頂點(diǎn),其數(shù)據(jù)域如下:
class Vertex<T> implements VertexInterface<T>, java.io.Serializable { private T label;//標(biāo)識(shí)標(biāo)點(diǎn),可以用不同類型來標(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)是否已訪問 private VertexInterface<T> previousVertex;//該頂點(diǎn)的前驅(qū)頂點(diǎn) private double cost;//頂點(diǎn)的權(quán)值,與邊的權(quán)值要區(qū)別開來
現(xiàn)在一一解釋Vertex類中定義的各個(gè)屬性:
label : 用來標(biāo)識(shí)頂點(diǎn),如圖中的 V0,V1,V2,V3,在實(shí)際代碼中,V0...V3 以字符串的形式表示,就可以用來標(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í),就可以訪問該頂點(diǎn)的所有鄰接點(diǎn)。因此,Vertex.java中就需要實(shí)現(xiàn)根據(jù)edgeList中存放的邊來遍歷 某條邊的終點(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的迭代器來實(shí)現(xiàn) * 由于頂點(diǎn)的鄰接點(diǎn)由Edge類封裝起來了--見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è)用來標(biāo)記它是否被訪問的屬性,是因?yàn)椋簩?shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu),是要用它去完成某些功能的,如遍歷、查找…… 而在圖的遍歷過程中,就需要標(biāo)記某個(gè)頂點(diǎn)是否被訪問了,因此:設(shè)置該屬性以便實(shí)現(xiàn)這些功能。那么,也就需要定義獲取頂點(diǎn)是否被訪問的isVisited()方法了。
public boolean isVisited() { return visited; }
previousVertex 屬性 ,在求圖中某兩個(gè)頂點(diǎn)之間的最短路徑時(shí),在從起始頂點(diǎn)遍歷過程中,需要記錄下遍歷到某個(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 屬性:用來表示頂點(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)將會(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)來實(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),可以用不同類型來標(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)是否已訪問 private VertexInterface<T> 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<Edge>();//是Vertex的屬性,說明每個(gè)頂點(diǎn)都有一個(gè)edgeList用來存儲(chǔ)所有與該頂點(diǎn)關(guān)系的邊 visited = false; previousVertex = null; cost = 0; } /** *Task: 這里用了一個(gè)單獨(dú)的類來表示邊,主要是考慮到帶權(quán)值的邊 *可以看出,Edge類封裝了一個(gè)頂點(diǎn)和一個(gè)double類型變量 *若不需要考慮權(quán)值,可以不需要單獨(dú)創(chuàng)建一個(gè)Edge類來表示邊,只需要一個(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的迭代器來實(shí)現(xiàn) * 由于頂點(diǎn)的鄰接點(diǎn)由Edge類封裝起來了--見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è)未被訪問的鄰接點(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; } }
上述內(nèi)容就是深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖,你們學(xué)到知識(shí)或技能了嗎?如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備,歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
當(dāng)前題目:深入淺析Java的數(shù)據(jù)結(jié)構(gòu)中的圖
文章起源:http://bm7419.com/article40/psoiho.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供Google、網(wǎng)站內(nèi)鏈、動(dòng)態(tài)網(wǎng)站、定制網(wǎng)站、App開發(fā)、手機(jī)網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)