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è)類(lèi)edge.java，作為vertex.java的內(nèi)部類(lèi)，edge.java如下：
|
1
2
3
|
protected class edge implements java.io.serializable { private vertexinterface<t> vertex;// 終點(diǎn) private double weight;//權(quán)值 |
edge類(lèi)中只有兩個(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)了（稱(chēng)之為這個(gè) 起點(diǎn)的鄰接表）。這樣的邊的特點(diǎn)是：邊的所有的起始點(diǎn)都相同。
但是為了表示帶權(quán)的邊，因此，新增加weight屬性，并用類(lèi)edge來(lái)封裝，這樣不管是帶權(quán)的邊還是不帶權(quán)的邊都可以用同一個(gè)edge類(lèi)來(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è)類(lèi)vertex.java 用來(lái)表示頂點(diǎn)，其數(shù)據(jù)域如下：
|
1
2
3
4
5
6
|
class vertex<t> implements vertexinterface<t>, java.io.serializable { private t label;//標(biāo)識(shí)標(biāo)點(diǎn),可以用不同類(lèi)型來(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類(lèi)中定義的各個(gè)屬性：
label : 用來(lái)標(biāo)識(shí)頂點(diǎn)，如圖中的 v0,v1,v2,v3，在實(shí)際代碼中，v0...v3 以字符串的形式表示，就可以用來(lái)標(biāo)識(shí)不同的頂點(diǎn)了。
因此，需要在vertex類(lèi)中添加獲得頂點(diǎn)標(biāo)識(shí)的方法---getlabel()
|
1
2
3
|
public t getlabel() { return label;} |
edgelist : 存放與該頂點(diǎn)關(guān)聯(lián)的邊。從上面edge.java中可以看到，edge的實(shí)質(zhì)是“頂點(diǎn)”，因?yàn)椋琫dge類(lèi)除去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)) 的迭代器了。
|
1
2
3
|
public iterator<vertexinterface<t>> getneighborinterator() { return new neighboriterator(); } |
迭代器的實(shí)現(xiàn)如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/**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)封裝起來(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()方法了。
|
1
2
3
|
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)的方法：
|
1
2
3
4
5
6
|
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)的方法如下：
|
1
2
3
4
5
6
|
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的完整代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
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)型來(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)來(lái)表示邊,主要是考慮到帶權(quán)值的邊 *可以看出,edge類(lèi)封裝了一個(gè)頂點(diǎn)和一個(gè)double類(lèi)型變量 *若不需要考慮權(quán)值,可以不需要單獨(dú)創(chuàng)建一個(gè)edge類(lèi)來(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 類(lèi)本身就代表頂點(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)封裝起來(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類(lèi)的屬性,因此先獲得一個(gè)遍歷edge對(duì)象的迭代器,取得edge對(duì)象,再獲得權(quán)值 * @author hapjin * * @param <double> 權(quán)值的類(lèi)型 */ 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)類(lèi)型的類(lèi)的equals() 決定 } return result; }} |
以上所述是小編給大家介紹的java數(shù)據(jù)結(jié)構(gòu)之圖(動(dòng)力節(jié)點(diǎn)java學(xué)院整理)，希望對(duì)大家有所幫助
