鄰接表無向圖的介紹
鄰接表無向圖是指通過鄰接表表示的無向圖。
上面的圖G1包含了”A,B,C,D,E,F,G”共7個頂點，而且包含了”(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)”共7條邊。
上圖右邊的矩陣是G1在內存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了”該頂點的鄰接點的序號”。例如，第2個頂點(頂點C)包含的鏈表所包含的節點的數據分別是”0,1,3”；而這”0,1,3”分別對應”A,B,D”的序號，”A,B,D”都是C的鄰接點。就是通過這種方式記錄圖的信息的。
鄰接表無向圖的代碼說明
1. 基本定義
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class ListUDG { // 鄰接表中表對應的鏈表的頂點 private class ENode { int ivex; // 該邊所指向的頂點的位置 ENode nextEdge; // 指向下一條弧的指針 } // 鄰接表中表的頂點 private class VNode { char data; // 頂點信息 ENode firstEdge; // 指向第一條依附該頂點的弧 } ; private VNode[] mVexs; // 頂點數組 ...} |
(01)ListUDG是鄰接表對應的結構體。mVexs則是保存頂點信息的一維數組。
(02)VNode是鄰接表頂點對應的結構體。data是頂點所包含的數據，而firstEdge是該頂點所包含鏈表的表頭指針。
(03)ENode是鄰接表頂點所包含的鏈表的節點對應的結構體。ivex是該節點所對應的頂點在vexs中的索引，而nextEdge是指向下一個節點的。
2.創建矩陣
這里介紹提供了兩個創建矩陣的方法。一個是用已知數據，另一個則需要用戶手動輸入數據。
2.1創建圖(用已提供的矩陣)
|
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
|
/* * 創建圖(用已提供的矩陣) * * 參數說明： * vexs -- 頂點數組 * edges -- 邊數組 */public ListUDG(char[] vexs, char[][] edges) { // 初始化"頂點數"和"邊數" int vlen = vexs.length; int elen = edges.length; // 初始化"頂點" mVexs = new VNode[vlen]; for (int i = 0; i < mVexs.length; i++) { mVexs[i] = new VNode(); mVexs[i].data = vexs[i]; mVexs[i].firstEdge = null; } // 初始化"邊" for (int i = 0; i < elen; i++) { // 讀取邊的起始頂點和結束頂點 char c1 = edges[i][0]; char c2 = edges[i][1]; // 讀取邊的起始頂點和結束頂點 int p1 = getPosition(edges[i][0]); int p2 = getPosition(edges[i][1]); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 將node1鏈接到"p1所在鏈表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 將node2鏈接到"p2所在鏈表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); }} |
該函數的作用是創建一個鄰接表無向圖。實際上，該方法創建的無向圖，就是上面圖G1。調用代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}};ListUDG pG;pG = new ListUDG(vexs, edges); |
2.2 創建圖(自己輸入)
|
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
|
/* * 創建圖(自己輸入數據) */public ListUDG() { // 輸入"頂點數"和"邊數" System.out.printf("input vertex number: "); int vlen = readint(); System.out.printf("input edge number: "); int elen = readint(); if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) { System.out.printf("input error: invalid parameters!\n"); return ; } // 初始化"頂點" mVexs = new VNode[vlen]; for (int i = 0; i < mVexs.length; i++) { System.out.printf("vertex(%d): ", i); mVexs[i] = new VNode(); mVexs[i].data = readchar(); mVexs[i].firstEdge = null; } // 初始化"邊" //mMatrix = new int[vlen][vlen]; for (int i = 0; i < elen; i++) { // 讀取邊的起始頂點和結束頂點 System.out.printf("edge(%d):", i); char c1 = readchar(); char c2 = readchar(); int p1 = getPosition(c1); int p2 = getPosition(c2); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 將node1鏈接到"p1所在鏈表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 將node2鏈接到"p2所在鏈表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); }} |
該函數是讀取用戶的輸入，將輸入的數據轉換成對應的無向圖。
鄰接表無向圖的完整源碼
|
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
|
import java.io.IOException;import java.util.Scanner;public class ListUDG { // 鄰接表中表對應的鏈表的頂點 private class ENode { int ivex; // 該邊所指向的頂點的位置 ENode nextEdge; // 指向下一條弧的指針 } // 鄰接表中表的頂點 private class VNode { char data; // 頂點信息 ENode firstEdge; // 指向第一條依附該頂點的弧 } ; private VNode[] mVexs; // 頂點數組 /* * 創建圖(自己輸入數據) */ public ListUDG() { // 輸入"頂點數"和"邊數" System.out.printf("input vertex number: "); int vlen = readint(); System.out.printf("input edge number: "); int elen = readint(); if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) { System.out.printf("input error: invalid parameters!\n"); return ; } // 初始化"頂點" mVexs = new VNode[vlen]; for (int i = 0; i < mVexs.length; i++) { System.out.printf("vertex(%d): ", i); mVexs[i] = new VNode(); mVexs[i].data = readchar(); mVexs[i].firstEdge = null; } // 初始化"邊" //mMatrix = new int[vlen][vlen]; for (int i = 0; i < elen; i++) { // 讀取邊的起始頂點和結束頂點 System.out.printf("edge(%d):", i); char c1 = readchar(); char c2 = readchar(); int p1 = getPosition(c1); int p2 = getPosition(c2); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 將node1鏈接到"p1所在鏈表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 將node2鏈接到"p2所在鏈表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } } /* * 創建圖(用已提供的矩陣) * * 參數說明： * vexs -- 頂點數組 * edges -- 邊數組 */ public ListUDG(char[] vexs, char[][] edges) { // 初始化"頂點數"和"邊數" int vlen = vexs.length; int elen = edges.length; // 初始化"頂點" mVexs = new VNode[vlen]; for (int i = 0; i < mVexs.length; i++) { mVexs[i] = new VNode(); mVexs[i].data = vexs[i]; mVexs[i].firstEdge = null; } // 初始化"邊" for (int i = 0; i < elen; i++) { // 讀取邊的起始頂點和結束頂點 char c1 = edges[i][0]; char c2 = edges[i][1]; // 讀取邊的起始頂點和結束頂點 int p1 = getPosition(edges[i][0]); int p2 = getPosition(edges[i][1]); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 將node1鏈接到"p1所在鏈表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 將node2鏈接到"p2所在鏈表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } } /* * 將node節點鏈接到list的最后 */ private void linkLast(ENode list, ENode node) { ENode p = list; while(p.nextEdge!=null) p = p.nextEdge; p.nextEdge = node; } /* * 返回ch位置 */ private int getPosition(char ch) { for (int i=0; i<mVexs.length; i++) if(mVexs[i].data==ch) return i; return -1; } /* * 讀取一個輸入字符 */ private char readchar() { char ch='0'; do { try { ch = (char)System.in.read(); } catch (IOException e) { e.printStackTrace(); } } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z'))); return ch; } /* * 讀取一個輸入字符 */ private int readint() { Scanner scanner = new Scanner(System.in); return scanner.nextint(); } /* * 打印矩陣隊列圖 */ public void print() { System.out.printf("List Graph:\n"); for (int i = 0; i < mVexs.length; i++) { System.out.printf("%d(%c): ", i, mVexs[i].data); ENode node = mVexs[i].firstEdge; while (node != null) { System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data); node = node.nextEdge; } System.out.printf("\n"); } } public static void main(String[] args) { char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; ListUDG pG; // 自定義"圖"(輸入矩陣隊列) //pG = new ListUDG(); // 采用已有的"圖" pG = new ListUDG(vexs, edges); pG.print(); // 打印圖 }} |
總結
以上就是本文關于鄰接表無向圖的Java語言實現完整源碼的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/coslay/article/details/47748419
