3
\$\begingroup\$

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

}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  • 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...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.