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