邻接表无向图的介绍
邻接表无向图是指通过邻接表表示的无向图。
上面的图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
