Skip to main content
edited body
Source Link
sanbhat
  • 133
  • 1
  • 6
//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(n1) 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;
    }

}
//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(n) 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;
    }

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

}
mjax
Source Link
Vogel612
  • 25.5k
  • 7
  • 59
  • 141

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 O(n)\$\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 x v\$v \times v\$ integer 2D array to map the vertices.

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 O(n).

In the various tutorials I have seen, Graphs contain only integer vertices and it becomes straight forward to represent them in v x v integer 2D array to map the vertices.

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.

Source Link
sanbhat
  • 133
  • 1
  • 6

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 O(n).

In the various tutorials I have seen, Graphs contain only integer vertices and it becomes straight forward to represent them in v x 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(n) 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);
    }

}