# Generic Graph using Adjacency matrix - Java

The main purpose of representing Graph using adjacency matrix method is, to check the vertex and its neighbor's existence in constant time proportional to $\mathcal{O}(n)$.

In the various tutorials I have seen, Graphs contain only integer vertices and it becomes straight forward to represent them in a $v \times v$ integer 2D array to map the vertices.

In real world, we might have to store a custom type Object as the graph vertex. For this, I have created a Graph implementation with Adjacency matrix. Can you please let me know of any feedback / improvements?

//V - type of Object stored on graph vertices
public class GraphAM<V> {

//Maps vertex with its adjacency matrix index. O(1) to retrieve index of a vertex
private Map<V, Integer> vertices;
//To get vertex using index at O(1) time
private List<V> verticesLookup;

//adjacency matrix
private int[][] adj;

private int index;

public GraphAM(int numVertices) {
adj = new int[numVertices][numVertices];
index = 0;
vertices = new HashMap<>();
verticesLookup = new ArrayList<>();
}

public void addEdge(V from, V to) {
addVertex(from);
addVertex(to);

int fromIndex = vertices.get(from);
int toIndex = vertices.get(to);
adj[fromIndex][toIndex] = 1;
}

private void addVertex(V v) {
if(!vertices.containsKey(v)) {
vertices.put(v, index);
verticesLookup.add(index, v);
index++;
}
}

public void bfs(V start) {
Queue<V> queue = new LinkedList<>();
boolean[] visited = new boolean[vertices.size()];

queue.add(start);
int index = vertices.get(start);
visited[index] = true;

while(!queue.isEmpty()) {
V v = queue.poll();
System.out.print(v + " ");

List<V> adjacentVertices = getAdjacentVertices(v);
for(V a : adjacentVertices) {
int adjInd = vertices.get(a);
if(!visited[adjInd]) {
queue.add(a);
visited[adjInd] = true;
}
}

}

}

public void dfs(V start) {
boolean[] visited = new boolean[vertices.size()];
dfs(start, visited);
}

private void dfs(V v, boolean[] visited) {
System.out.print(v + " ");
int index = vertices.get(v);
visited[index] = true;

List<V> adjacentVertices = getAdjacentVertices(v);
for(V a : adjacentVertices) {
int aIndex = vertices.get(a);
if(!visited[aIndex]) {
dfs(a, visited);
}
}
}

private List<V> getAdjacentVertices(V v) {
int index = vertices.get(v);
List<V> result = new ArrayList<>();
for(int i=0; i<adj[index].length; i++) {
if(adj[index][i] == 1) {
result.add(verticesLookup.get(i));
}
}
return result;
}

}


Main class

class Main {

public static void main(String[] args) {
GraphAM<Integer> g = new GraphAM<>(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

System.out.println("Following is Breadth First Traversal "+
"(starting from vertex 2)");

g.bfs(2);

System.out.println("\nFollowing is Depth First Traversal "+
"(starting from vertex 2)");

g = new GraphAM<>(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

g.dfs(2);
}

}


## 1 Answer

• You can simplify the mapping you are using to get from vertex to it's associated object. Instead of using a List<V>, which can only guarantee $\mathcal{O}(n)$ lookup time, you could just use an array.

• Comments restating what's known should be removed, comments that can be made obsolete through refactoring should prompt that refactoring:

public class GraphAM<V> {
private Map<V, Integer> vertexToIndex;
private V[] indexToVertex;

private int[][] adjacencyMatrix;
private int index;

• vertices (aka vertexToIndex can be eagerly initialized.

• all private fields (apart from index) should be marked final.

• Instead of passing numVertices to the constructor, you should consider passing a Collection<V>, which removes the need to deal with adding vertices in addEdge.

• Finally instead of using a boolean[] for visited, a Set<V> is significantly more obvious. It might come with a minor performance penalty though.

• Finally the search functions do not search for anything... they're just performing an exhaustive traversal and are accordingly useless in their current form...