trjhtr

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 $mathcalO(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);
 

• 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 $mathcalO(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...