# 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;

private int index;

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

public void addEdge(V from, V to) {

int fromIndex = vertices.get(from);
int toIndex = vertices.get(to);
}

if(!vertices.containsKey(v)) {
vertices.put(v, index);
index++;
}
}

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

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

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

}
}

}

}

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;

int aIndex = vertices.get(a);
if(!visited[aIndex]) {
dfs(a, visited);
}
}
}

int index = vertices.get(v);
List<V> result = new ArrayList<>();
}
}
return result;
}

}


Main class

class Main {

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

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.dfs(2);
}

}


• 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;


• 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.