-
Notifications
You must be signed in to change notification settings - Fork 155
/
Ex_4_1_03.java
126 lines (109 loc) · 2.37 KB
/
Ex_4_1_03.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
package Ch_4_1;
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;
import tools.PrintUtil;
/**
* Created by HuGuodong on 2/4/20.
*/
public class Ex_4_1_03 {
public static void main(String[] args) {
_Graph g = new _Graph(new In("algdata/tinyG.txt"));
PrintUtil.printSepLine("original");
StdOut.println(g);
_Graph another = new _Graph(g);
PrintUtil.printSepLine("copy");
another.addEdge(10, 11);
StdOut.println(another);
// -----------------------original-------------------------------
// 13 vertices, 13 edges
// 0: 6 2 1 5
// 1: 0
// 2: 0
// 3: 5 4
// 4: 5 6 3
// 5: 3 4 0
// 6: 0 4
// 7: 8
// 8: 7
// 9: 11 10 12
// 10: 9
// 11: 9 12
// 12: 11 9
//
// -----------------------copy-------------------------------
// 13 vertices, 13 edges
// 0: 6 2 1 5
// 1: 0
// 2: 0
// 3: 5 4
// 4: 5 6 3
// 5: 3 4 0
// 6: 0 4
// 7: 8
// 8: 7
// 9: 11 10 12
// 10: 9
// 11: 9 12
// 12: 11 9
}
static class _Graph {
private final int V;
private int E;
private Bag<Integer>[] adj;
public _Graph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<>();
}
}
public _Graph(In in) {
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
addEdge(v, w);
}
}
public _Graph(_Graph src) {
this(src.V);
Stack<Integer> stack = new Stack<>();
for (int v = 0; v < V; v++) {
for (int w : src.adj[v]) {
stack.push(w);
}
while (!stack.isEmpty()) {
adj[v].add(stack.pop());
}
}
this.E = src.E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public int V() {
return V;
}
public int E() {
return E;
}
@Override
public String toString() {
String result = String.format("%d vertices, %d edges\n", V, E);
for (int v = 0; v < V; v++) {
result += (v + ":");
for (int w : adj[v]) {
result += (" " + w);
}
result += "\n";
}
return result;
}
}
}