forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMatrixGraphs.java
More file actions
336 lines (296 loc) · 9.85 KB
/
MatrixGraphs.java
File metadata and controls
336 lines (296 loc) · 9.85 KB
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
package DataStructures.Graphs;
import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* Implementation of a graph in a matrix form
* Also known as an adjacency matrix representation
* [Adjacency matrix - Wikipedia](https://en.wikipedia.org/wiki/Adjacency_matrix)
*
* @author Unknown
*/
public class MatrixGraphs {
public static void main(String args[]) {
AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(10);
graph.addEdge(1, 2);
graph.addEdge(1, 5);
graph.addEdge(2, 5);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 9);
graph.addEdge(9, 1);
graph.addEdge(9, 8);
graph.addEdge(1, 8);
graph.addEdge(5, 6);
System.out.println("The graph matrix:");
System.out.println(graph);
System.out.println("Depth first order beginning at node '1':");
System.out.println(graph.depthFirstOrder(1));
System.out.println("Breadth first order beginning at node '1':");
System.out.println(graph.breadthFirstOrder(1));
}
}
/**
* AdjacencyMatrixGraph Implementation
*/
class AdjacencyMatrixGraph {
/**
* The number of vertices in the graph
*/
private int _numberOfVertices;
/**
* The number of edges in the graph
*/
private int _numberOfEdges;
/**
* The adjacency matrix for the graph
*/
private int[][] _adjacency;
/**
* Static variables to define whether or not an edge exists in the
* adjacency matrix
*/
static final int EDGE_EXIST = 1;
static final int EDGE_NONE = 0;
/**
* Constructor
*/
public AdjacencyMatrixGraph(int givenNumberOfVertices) {
this.setNumberOfVertices(givenNumberOfVertices);
this.setNumberOfEdges(0);
this.setAdjacency(new int[givenNumberOfVertices][givenNumberOfVertices]);
for (int i = 0; i < givenNumberOfVertices; i++) {
for (int j = 0; j < givenNumberOfVertices; j++) {
this.adjacency()[i][j] = AdjacencyMatrixGraph.EDGE_NONE;
}
}
}
/**
* Updates the number of vertices in the graph
*
* @param newNumberOfVertices the new number of vertices
*/
private void setNumberOfVertices(int newNumberOfVertices) {
this._numberOfVertices = newNumberOfVertices;
}
/**
* Getter for `this._numberOfVertices`
*
* @return the number of vertices in the graph
*/
public int numberOfVertices() {
return this._numberOfVertices;
}
/**
* Updates the number of edges in the graph
*
* @param newNumberOfEdges
* */
private void setNumberOfEdges(int newNumberOfEdges) {
this._numberOfEdges = newNumberOfEdges;
}
/**
* Getter for `this._numberOfEdges`
*
* @return the number of edges
*/
public int numberOfEdges() {
return this._numberOfEdges;
}
/**
* Sets a new matrix as the adjacency matrix
*
* @param newAdjacency the new adjaceny matrix
*/
private void setAdjacency(int[][] newAdjacency) {
this._adjacency = newAdjacency;
}
/**
* Getter for the adjacency matrix
*
* @return the adjacency matrix
*/
private int[][] adjacency() {
return this._adjacency;
}
/**
* Checks if two vertices are connected by an edge
*
* @param from the parent vertex to check for adjacency
* @param to the child vertex to check for adjacency
* @return whether or not the vertices are adjancent
*/
private boolean adjacencyOfEdgeDoesExist(int from, int to) {
return (this.adjacency()[from][to] != AdjacencyMatrixGraph.EDGE_NONE);
}
/**
* Checks if a particular vertex exists in a graph
*
* @param aVertex the vertex to check for existence
* @return whether or not the vertex exists
*/
public boolean vertexDoesExist(int aVertex) {
if (aVertex >= 0 && aVertex < this.numberOfVertices()) {
return true;
} else {
return false;
}
}
/**
* Checks if two vertices are connected by an edge
*
* @param from the parent vertex to check for adjacency
* @param to the child vertex to check for adjacency
* @return whether or not the vertices are adjancent
*/
public boolean edgeDoesExist(int from, int to) {
if (this.vertexDoesExist(from) && this.vertexDoesExist(to)) {
return (this.adjacencyOfEdgeDoesExist(from, to));
}
return false;
}
/**
* This method adds an edge to the graph between two specified vertices
*
* @param from the data of the vertex the edge is from
* @param to the data of the vertex the edge is going to
* @return returns true if the edge did not exist, return false if it already did
*/
public boolean addEdge(int from, int to) {
if (this.vertexDoesExist(from) && this.vertexDoesExist(to)) {
if (!this.adjacencyOfEdgeDoesExist(from, to)) {
this.adjacency()[from][to] = AdjacencyMatrixGraph.EDGE_EXIST;
this.adjacency()[to][from] = AdjacencyMatrixGraph.EDGE_EXIST;
this.setNumberOfEdges(this.numberOfEdges() + 1);
return true;
}
}
return false;
}
/**
* this method removes an edge from the graph between two specified vertices
*
* @param from the data of the vertex the edge is from
* @param to the data of the vertex the edge is going to
* @return returns false if the edge doesn't exist, returns true if the edge exists and is removed
*/
public boolean removeEdge(int from, int to) {
if (!this.vertexDoesExist(from) || !this.vertexDoesExist(to)) {
if (this.adjacencyOfEdgeDoesExist(from, to)) {
this.adjacency()[from][to] = AdjacencyMatrixGraph.EDGE_NONE;
this.adjacency()[to][from] = AdjacencyMatrixGraph.EDGE_NONE;
this.setNumberOfEdges(this.numberOfEdges() - 1);
return true;
}
}
return false;
}
/**
* This method returns a list of the vertices in a depth first order
* beginning with the specified vertex
*
* @param startVertex the vertex to begin the traversal
* @return the list of the ordered vertices
*/
public List<Integer> depthFirstOrder(int startVertex) {
// If the startVertex is invalid, return an empty list
if (startVertex >= _numberOfVertices || startVertex < 0)
return new ArrayList<Integer>();
// Create an array to track the visited vertices
boolean[] visited = new boolean[_numberOfVertices];
// Create a list to keep track of the order of our traversal
ArrayList<Integer> orderList = new ArrayList<Integer>();
// Perform our DFS algorithm
depthFirstOrder(startVertex, visited, orderList);
return orderList;
}
/**
* Helper method for public depthFirstOrder(int) that will perform
* a depth first traversal recursively on the graph
*
* @param currentVertex the currently exploring vertex
* @param visited the array of values denoting whether or not that vertex has been visited
* @param orderList the list to add vertices to as they are visited
*/
private void depthFirstOrder(int currentVertex, boolean[] visited, List<Integer> orderList) {
// If this vertex has already been visited, do nothing and return
if (visited[currentVertex])
return;
// Visit the currentVertex by marking it as visited and adding it
// to the orderList
visited[currentVertex] = true;
orderList.add(currentVertex);
// Get the adjacency array for this vertex
int[] adjacent = _adjacency[currentVertex];
for (int i = 0; i < adjacent.length; i++)
// If an edge exists between the currentVertex and the vertex
// we are considering exploring, recurse on it
if (adjacent[i] == AdjacencyMatrixGraph.EDGE_EXIST)
depthFirstOrder(i, visited, orderList);
}
/**
* This method returns a list of the vertices in a breadth first order
* beginning with the specified vertex
*
* @param startVertex the vertext to begin the traversal
* @return the list of the ordered vertices
*/
public List<Integer> breadthFirstOrder(int startVertex) {
// If the specified startVertex is invalid, return an empty list
if (startVertex >= _numberOfVertices || startVertex < 0)
return new ArrayList<Integer>();
// Create an array to keep track of the visited vertices
boolean[] visited = new boolean[_numberOfVertices];
// Create a list to keep track of the ordered vertices
ArrayList<Integer> orderList = new ArrayList<Integer>();
// Create a queue for our BFS algorithm and add the startVertex
// to the queue
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(startVertex);
// Continue until the queue is empty
while (! queue.isEmpty()) {
// Remove the first vertex in the queue
int currentVertex = queue.poll();
// If we've visited this vertex, skip it
if (visited[currentVertex])
continue;
// We now visit this vertex by adding it to the orderList and
// marking it as visited
orderList.add(currentVertex);
visited[currentVertex] = true;
// Get the adjacency array for the currentVertex and
// check each node
int[] adjacent = _adjacency[currentVertex];
for (int vertex = 0; vertex < adjacent.length; vertex++)
// If an edge exists between the current vertex and the
// vertex we are considering exploring, we add it to the queue
if (adjacent[vertex] == AdjacencyMatrixGraph.EDGE_EXIST)
queue.add(vertex);
}
return orderList;
}
/**
* this gives a list of vertices in the graph and their adjacencies
*
* @return returns a string describing this graph
*/
public String toString() {
String s = " ";
for (int i = 0; i < this.numberOfVertices(); i++) {
s = s + String.valueOf(i) + " ";
}
s = s + " \n";
for (int i = 0; i < this.numberOfVertices(); i++) {
s = s + String.valueOf(i) + " : ";
for (int j = 0; j < this.numberOfVertices(); j++) {
s = s + String.valueOf(this._adjacency[i][j]) + " ";
}
s = s + "\n";
}
return s;
}
}