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