要存儲(chǔ)一個(gè)圖，我們知道圖既有結(jié)點(diǎn)，又有邊，對(duì)于有權(quán)圖來說，每條邊上還帶有權(quán)值。常用的圖的存儲(chǔ)結(jié)構(gòu)主要有以下二種：
鄰接矩陣
鄰接表
鄰接矩陣
我們知道，要表示結(jié)點(diǎn)，我們可以用一個(gè)一維數(shù)組來表示，然而對(duì)于結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，則無法簡(jiǎn)單地用一維數(shù)組來表示了，我們可以用二維數(shù)組來表示，也就是一個(gè)矩陣形式的表示方法。
我們假設(shè)a是這個(gè)二維數(shù)組，那么a中的一個(gè)元素aij不僅體現(xiàn)出了結(jié)點(diǎn)vi和結(jié)點(diǎn)vj的關(guān)系，而且aij的值正可以表示權(quán)值的大小。
以下是一個(gè)無向圖的鄰接矩陣表示示例：
從上圖我們可以看到，無向圖的鄰接矩陣是對(duì)稱矩陣，也一定是對(duì)稱矩陣。且其左上角到右下角的對(duì)角線上值為零（對(duì)角線上表示的是相同的結(jié)點(diǎn)）
有向圖的鄰接矩陣是怎樣的呢？
對(duì)于帶權(quán)圖，aij的值可用來表示權(quán)值的大小，上面兩張圖是不帶權(quán)的圖，因此它們值都是1。
鄰接表
我們知道，圖的鄰接矩陣存儲(chǔ)方法用的是一個(gè)n*n的矩陣，當(dāng)這個(gè)矩陣是稠密的矩陣（比如說當(dāng)圖是完全圖的時(shí)候），那么當(dāng)然選擇用鄰接矩陣存儲(chǔ)方法。
可是如果這個(gè)矩陣是一個(gè)稀疏的矩陣呢，這個(gè)時(shí)候鄰接表存儲(chǔ)結(jié)構(gòu)就是一種更節(jié)省空間的存儲(chǔ)結(jié)構(gòu)了。
對(duì)于上文中的無向圖，我們可以用鄰接表來表示，如下：
每一個(gè)結(jié)點(diǎn)后面所接的結(jié)點(diǎn)都是它的鄰接結(jié)點(diǎn)。
鄰接矩陣與鄰接表的比較
當(dāng)圖中結(jié)點(diǎn)數(shù)目較小且邊較多時(shí)，采用鄰接矩陣效率更高。
當(dāng)節(jié)點(diǎn)數(shù)目遠(yuǎn)大且邊的數(shù)目遠(yuǎn)小于相同結(jié)點(diǎn)的完全圖的邊數(shù)時(shí)，采用鄰接表存儲(chǔ)結(jié)構(gòu)更有效率。
鄰接矩陣的java實(shí)現(xiàn)
鄰接矩陣模型類
鄰接矩陣模型類的類名為amwgraph.java，能夠通過該類構(gòu)造一個(gè)鄰接矩陣表示的圖，且提供插入結(jié)點(diǎn)，插入邊，取得某一結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)和下一個(gè)鄰接結(jié)點(diǎ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
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
|
import java.util.arraylist;import java.util.linkedlist;/** * @description 鄰接矩陣模型類 * @author beanlam * @time 2015.4.17 */public class amwgraph { private arraylist vertexlist;//存儲(chǔ)點(diǎn)的鏈表 private int[][] edges;//鄰接矩陣，用來存儲(chǔ)邊 private int numofedges;//邊的數(shù)目 public amwgraph(int n) { //初始化矩陣，一維數(shù)組，和邊的數(shù)目 edges=new int[n][n]; vertexlist=new arraylist(n); numofedges=0; } //得到結(jié)點(diǎn)的個(gè)數(shù) public int getnumofvertex() { return vertexlist.size(); } //得到邊的數(shù)目 public int getnumofedges() { return numofedges; } //返回結(jié)點(diǎn)i的數(shù)據(jù) public object getvaluebyindex(int i) { return vertexlist.get(i); } //返回v1,v2的權(quán)值 public int getweight(int v1,int v2) { return edges[v1][v2]; } //插入結(jié)點(diǎn) public void insertvertex(object vertex) { vertexlist.add(vertexlist.size(),vertex); } //插入結(jié)點(diǎn) public void insertedge(int v1,int v2,int weight) { edges[v1][v2]=weight; numofedges++; } //刪除結(jié)點(diǎn) public void deleteedge(int v1,int v2) { edges[v1][v2]=0; numofedges--; } //得到第一個(gè)鄰接結(jié)點(diǎn)的下標(biāo) public int getfirstneighbor(int index) { for(int j=0;j<vertexlist.size();j++) { if (edges[index][j]>0) { return j; } } return -1; } //根據(jù)前一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)來取得下一個(gè)鄰接結(jié)點(diǎn) public int getnextneighbor(int v1,int v2) { for (int j=v2+1;j<vertexlist.size();j++) { if (edges[v1][j]>0) { return j; } } return -1; }} |
鄰接矩陣模型類的測(cè)試
接下來根據(jù)下面一個(gè)有向圖來設(shè)置測(cè)試該模型類
testamwgraph.java測(cè)試程序如下所示：
|
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
|
/** * @description amwgraph類的測(cè)試類 * @author beanlam * @time 2015.4.17 */public class testamwgraph { public static void main(string args[]) { int n=4,e=4;//分別代表結(jié)點(diǎn)個(gè)數(shù)和邊的數(shù)目 string labels[]={"v1","v1","v3","v4"};//結(jié)點(diǎn)的標(biāo)識(shí) amwgraph graph=new amwgraph(n); for(string label:labels) { graph.insertvertex(label);//插入結(jié)點(diǎn) } //插入四條邊 graph.insertedge(0, 1, 2); graph.insertedge(0, 2, 5); graph.insertedge(2, 3, 8); graph.insertedge(3, 0, 7); system.out.println("結(jié)點(diǎn)個(gè)數(shù)是："+graph.getnumofvertex()); system.out.println("邊的個(gè)數(shù)是："+graph.getnumofedges()); graph.deleteedge(0, 1);//刪除<v1,v2>邊 system.out.println("刪除<v1,v2>邊后..."); system.out.println("結(jié)點(diǎn)個(gè)數(shù)是："+graph.getnumofvertex()); system.out.println("邊的個(gè)數(shù)是："+graph.getnumofedges()); }} |
控制臺(tái)輸出結(jié)果如下圖所示：
總結(jié)
以上就是本文關(guān)于java語言描述存儲(chǔ)結(jié)構(gòu)與鄰接矩陣代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。
原文鏈接：https://segmentfault.com/a/1190000002685782
