Generic Graph using Adjacency matrix - Java

Question

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);
 }
}

Answer 1

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