1 import java.util.*;
2
3 public class UnweightedGraph<V> implements Graph<V> {
4 protected List<V> vertices = new ArrayList<>();
5 protected List<List<Edge>> neighbors
6 = new ArrayList<>();
7
8
9 public UnweightedGraph() {
10 }
11
12
13 public UnweightedGraph(V[] vertices, int[][] edges) {
14 for (int i = 0; i < vertices.length; i++)
15 addVertex(vertices[i]);
16
17 createAdjacencyLists(edges, vertices.length);
18 }
19
20
21 public UnweightedGraph(List<V> vertices, List<Edge> edges) {
22 for (int i = 0; i < vertices.size(); i++)
23 addVertex(vertices.get(i));
24
25 createAdjacencyLists(edges, vertices.size());
26 }
27
28
29 public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
30 for (int i = 0; i < numberOfVertices; i++)
31 addVertex((V)(Integer.valueOf(i)));
32
33 createAdjacencyLists(edges, numberOfVertices);
34 }
35
36
37 public UnweightedGraph(int[][] edges, int numberOfVertices) {
38 for (int i = 0; i < numberOfVertices; i++)
39 addVertex((V)(Integer.valueOf(i)));
40
41 createAdjacencyLists(edges, numberOfVertices);
42 }
43
44
45 private void createAdjacencyLists(
46 int[][] edges, int numberOfVertices) {
47 for (int i = 0; i < edges.length; i++) {
48 addEdge(edges[i][0], edges[i][1]);
49 }
50 }
51
52
53 private void createAdjacencyLists(
54 List<Edge> edges, int numberOfVertices) {
55 for (Edge edge: edges) {
56 addEdge(edge.u, edge.v);
57 }
58 }
59
60 @Override
61 public int getSize() {
62 return vertices.size();
63 }
64
65 @Override
66 public List<V> getVertices() {
67 return vertices;
68 }
69
70 @Override
71 public V getVertex(int index) {
72 return vertices.get(index);
73 }
74
75 @Override
76 public int getIndex(V v) {
77 return vertices.indexOf(v);
78 }
79
80 @Override
81 public List<Integer> getNeighbors(int index) {
82 List<Integer> result = new ArrayList<>();
83 for (Edge e: neighbors.get(index))
84 result.add(e.v);
85
86 return result;
87 }
88
89 @Override
90 public int getDegree(int v) {
91 return neighbors.get(v).size();
92 }
93
94 @Override
95 public void printEdges() {
96 for (int u = 0; u < neighbors.size(); u++) {
97 System.out.print(getVertex(u) + " (" + u + "): ");
98 for (Edge e: neighbors.get(u)) {
99 System.out.print("(" + getVertex(e.u) + ", " +
100 getVertex(e.v) + ") ");
101 }
102 System.out.println();
103 }
104 }
105
106 @Override
107 public void clear() {
108 vertices.clear();
109 neighbors.clear();
110 }
111
112 @Override
113 public boolean addVertex(V vertex) {
114 if (!vertices.contains(vertex)) {
115 vertices.add(vertex);
116 neighbors.add(new ArrayList<Edge>());
117 return true;
118 }
119 else {
120 return false;
121 }
122 }
123
124 @Override
125 public boolean addEdge(Edge e) {
126 if (e.u < 0 || e.u > getSize() - 1)
127 throw new IllegalArgumentException("No such index: " + e.u);
128
129 if (e.v < 0 || e.v > getSize() - 1)
130 throw new IllegalArgumentException("No such index: " + e.v);
131
132 if (!neighbors.get(e.u).contains(e)) {
133 neighbors.get(e.u).add(e);
134 return true;
135 }
136 else {
137 return false;
138 }
139 }
140
141 @Override
142 public boolean addEdge(int u, int v) {
143 return addEdge(new Edge(u, v));
144 }
145
146 @Override
147
148 public SearchTree dfs(int v) {
149 List<Integer> searchOrder = new ArrayList<>();
150 int[] parent = new int[vertices.size()];
151 for (int i = 0; i < parent.length; i++)
152 parent[i] = -1;
153
154
155 boolean[] isVisited = new boolean[vertices.size()];
156
157
158 dfs(v, parent, searchOrder, isVisited);
159
160
161 return new SearchTree(v, parent, searchOrder);
162 }
163
164
165 private void dfs(int v, int[] parent, List<Integer> searchOrder,
166 boolean[] isVisited) {
167
168 searchOrder.add(v);
169 isVisited[v] = true;
170
171 for (Edge e : neighbors.get(v)) {
172 int w = e.v;
173 if (!isVisited[w]) {
174 parent[w] = v;
175 dfs(w, parent, searchOrder, isVisited);
176 }
177 }
178 }
179
180 @Override
181
182 public SearchTree bfs(int v) {
183 List<Integer> searchOrder = new ArrayList<>();
184 int[] parent = new int[vertices.size()];
185 for (int i = 0; i < parent.length; i++)
186 parent[i] = -1;
187
188 java.util.LinkedList<Integer> queue =
189 new java.util.LinkedList<>();
190 boolean[] isVisited = new boolean[vertices.size()];
191 queue.offer(v);
192 isVisited[v] = true;
193
194 while (!queue.isEmpty()) {
195 int u = queue.poll();
196 searchOrder.add(u);
197 for (Edge e: neighbors.get(u)) {
198 int w = e.v;
199 if (!isVisited[w]) {
200 queue.offer(w);
201 parent[w] = u;
202 isVisited[w] = true;
203 }
204 }
205 }
206
207 return new SearchTree(v, parent, searchOrder);
208 }
209
210
211
212 public class SearchTree {
213 private int root;
214 private int[] parent;
215 private List<Integer> searchOrder;
216
217
218 public SearchTree(int root, int[] parent,
219 List<Integer> searchOrder) {
220 this.root = root;
221 this.parent = parent;
222 this.searchOrder = searchOrder;
223 }
224
225
226 public int getRoot() {
227 return root;
228 }
229
230
231 public int getParent(int v) {
232 return parent[v];
233 }
234
235
236 public List<Integer> getSearchOrder() {
237 return searchOrder;
238 }
239
240
241 public int getNumberOfVerticesFound() {
242 return searchOrder.size();
243 }
244
245
246 public List<V> getPath(int index) {
247 ArrayList<V> path = new ArrayList<>();
248
249 do {
250 path.add(vertices.get(index));
251 index = parent[index];
252 }
253 while (index != -1);
254
255 return path;
256 }
257
258
259 public void printPath(int index) {
260 List<V> path = getPath(index);
261 System.out.print("A path from " + vertices.get(root) + " to " +
262 vertices.get(index) + ": ");
263 for (int i = path.size() - 1; i >= 0; i--)
264 System.out.print(path.get(i) + " ");
265 }
266
267
268 public void printTree() {
269 System.out.println("Root is: " + vertices.get(root));
270 System.out.print("Edges: ");
271 for (int i = 0; i < parent.length; i++) {
272 if (parent[i] != -1) {
273
274 System.out.print("(" + vertices.get(parent[i]) + ", " +
275 vertices.get(i) + ") ");
276 }
277 }
278 System.out.println();
279 }
280 }
281
282 @Override
283 public boolean remove(V v) {
284 return true;
285 }
286
287 @Override
288 public boolean remove(int u, int v) {
289 return true;
290 }
291 }