-
Notifications
You must be signed in to change notification settings - Fork 768
/
ListDG.java
345 lines (300 loc) · 9.93 KB
/
ListDG.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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
/**
* Java: 无回路有向图(Directed Acyclic Graph)的拓扑排序
* 该DAG图是通过邻接表实现的。
*
* @author skywang
* @date 2014/04/22
*/
import java.io.IOException;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
public class ListDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private List<VNode> mVexs; // 顶点数组
/*
* 创建图(自己输入数据)
*/
public ListDG() {
// 输入"顶点数"和"边数"
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 ArrayList<VNode>();
for (int i = 0; i < vlen; i++) {
System.out.printf("vertex(%d): ", i);
// 新建VNode
VNode vnode = new VNode();
vnode.data = readChar();
vnode.firstEdge = null;
// 将vnode添加到数组mVexs中
mVexs.add(vnode);
}
// 初始化"边"
//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.get(p1).firstEdge == null)
mVexs.get(p1).firstEdge = node1;
else
linkLast(mVexs.get(p1).firstEdge, node1);
}
}
/*
* 创建图(用已提供的矩阵)
*
* 参数说明:
* vexs -- 顶点数组
* edges -- 边数组
*/
public ListDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new ArrayList<VNode>();
for (int i = 0; i < vlen; i++) {
// 新建VNode
VNode vnode = new VNode();
vnode.data = vexs[i];
vnode.firstEdge = null;
// 将vnode添加到数组mVexs中
mVexs.add(vnode);
}
// 初始化"边"
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.get(p1).firstEdge == null)
mVexs.get(p1).firstEdge = node1;
else
linkLast(mVexs.get(p1).firstEdge, node1);
}
}
/*
* 将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.size(); i++)
if(mVexs.get(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();
}
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
ENode node;
visited[i] = true;
System.out.printf("%c ", mVexs.get(i).data);
node = mVexs.get(i).firstEdge;
while (node != null) {
if (!visited[node.ivex])
DFS(node.ivex, visited);
node = node.nextEdge;
}
}
/*
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[mVexs.size()]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.size(); i++)
visited[i] = false;
System.out.printf("== DFS: ");
for (int i = 0; i < mVexs.size(); i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
/*
* 广度优先搜索(类似于树的层次遍历)
*/
public void BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.size()]; // 辅组队列
boolean[] visited = new boolean[mVexs.size()]; // 顶点访问标记
for (int i = 0; i < mVexs.size(); i++)
visited[i] = false;
System.out.printf("== BFS: ");
for (int i = 0; i < mVexs.size(); i++) {
if (!visited[i]) {
visited[i] = true;
System.out.printf("%c ", mVexs.get(i).data);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
ENode node = mVexs.get(j).firstEdge;
while (node != null) {
int k = node.ivex;
if (!visited[k])
{
visited[k] = true;
System.out.printf("%c ", mVexs.get(k).data);
queue[rear++] = k;
}
node = node.nextEdge;
}
}
}
System.out.printf("\n");
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("== List Graph:\n");
for (int i = 0; i < mVexs.size(); i++) {
System.out.printf("%d(%c): ", i, mVexs.get(i).data);
ENode node = mVexs.get(i).firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs.get(node.ivex).data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
/*
* 拓扑排序
*
* 返回值:
* -1 -- 失败(由于内存不足等原因导致)
* 0 -- 成功排序,并输入结果
* 1 -- 失败(该有向图是有环的)
*/
public int topologicalSort() {
int index = 0;
int num = mVexs.size();
int[] ins; // 入度数组
char[] tops; // 拓扑排序结果数组,记录每个节点的排序后的序号。
Queue<Integer> queue; // 辅组队列
ins = new int[num];
tops = new char[num];
queue = new LinkedList<Integer>();
// 统计每个顶点的入度数
for(int i = 0; i < num; i++) {
ENode node = mVexs.get(i).firstEdge;
while (node != null) {
ins[node.ivex]++;
node = node.nextEdge;
}
}
// 将所有入度为0的顶点入队列
for(int i = 0; i < num; i ++)
if(ins[i] == 0)
queue.offer(i); // 入队列
while (!queue.isEmpty()) { // 队列非空
int j = queue.poll().intValue(); // 出队列。j是顶点的序号
tops[index++] = mVexs.get(j).data; // 将该顶点添加到tops中,tops是排序结果
ENode node = mVexs.get(j).firstEdge;// 获取以该顶点为起点的出边队列
// 将与"node"关联的节点的入度减1;
// 若减1之后,该节点的入度为0;则将该节点添加到队列中。
while(node != null) {
// 将节点(序号为node.ivex)的入度减1。
ins[node.ivex]--;
// 若节点的入度为0,则将其"入队列"
if( ins[node.ivex] == 0)
queue.offer(node.ivex); // 入队列
node = node.nextEdge;
}
}
if(index != num) {
System.out.printf("Graph has a cycle\n");
return 1;
}
// 打印拓扑排序结果
System.out.printf("== TopSort: ");
for(int i = 0; i < num; i ++)
System.out.printf("%c ", tops[i]);
System.out.printf("\n");
return 0;
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'G'},
{'B', 'A'},
{'B', 'D'},
{'C', 'F'},
{'C', 'G'},
{'D', 'E'},
{'D', 'F'}};
ListDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new ListDG();
// 采用已有的"图"
pG = new ListDG(vexs, edges);
pG.print(); // 打印图
//pG.DFS(); // 深度优先遍历
//pG.BFS(); // 广度优先遍历
pG.topologicalSort(); // 拓扑排序
}
}