Java Code For Graph Data Structure Implementation

import java.util.*


public class Graph {


    private HashMap<Integer, ArrayList<Integer>> map;


    public Graph() {
        map = new HashMap<Integer, ArrayList<Integer>>();
    }


    public void addVertex(int vertex) {
        if (!map.containsKey(vertex)) {
            map.put(vertex, new ArrayList<Integer>());
        }
    }


    public void addEdge(int vertex1, int vertex2) {
        if (!map.containsKey(vertex1)) {
            addVertex(vertex1);
        }
        if (!map.containsKey(vertex2)) {
            addVertex(vertex2);
        }
        map.get(vertex1).add(vertex2);
        map.get(vertex2).add(vertex1); // remove this line if you want a directed graph
    }


    public ArrayList<Integer> getAdjacentVertices(int vertex) {
        if (map.containsKey(vertex)) {
            return map.get(vertex);
        }
        return null;
    }
    
    public void removeEdge(int vertex1, int vertex2) {
        if (map.containsKey(vertex1) && map.containsKey(vertex2)) {
            map.get(vertex1).remove(Integer.valueOf(vertex2));
            map.get(vertex2).remove(Integer.valueOf(vertex1)); // remove this line if you want a directed graph
        }
    }


    public void removeVertex(int vertex) {
        if (map.containsKey(vertex)) {
            ArrayList<Integer> adjacentVertices = map.get(vertex);
            for (int adjacentVertex : adjacentVertices) {
                removeEdge(vertex, adjacentVertex);
            }
            map.remove(vertex);
        }
    }


    public boolean isConnected() {
        if (map.size() == 0 || map.size() == 1) {
            return true;
        }
        Set<Integer> visited = new HashSet<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        int startVertex = map.keySet().iterator().next();
        stack.push(startVertex);
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            visited.add(vertex);
            ArrayList<Integer> adjacentVertices = map.get(vertex);
            for (int adjacentVertex : adjacentVertices) {
                if (!visited.contains(adjacentVertex)) {
                    stack.push(adjacentVertex);
                }
            }
        }
        return visited.size() == map.size();
    }


    public void DFS(int startVertex) {
        Set<Integer> visited = new HashSet<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(startVertex);
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            if (!visited.contains(vertex)) {
                System.out.print(vertex + " ");
                visited.add(vertex);
                ArrayList<Integer> adjacentVertices = map.get(vertex);
                for (int adjacentVertex : adjacentVertices) {
                    if (!visited.contains(adjacentVertex)) {
                        stack.push(adjacentVertex);
                    }
                }
            }
        }
    }


    public void printGraph() {
        for (int vertex : map.keySet()) {
            System.out.print(vertex + ": ");
            for (int adjacentVertex : map.get(vertex)) {
                System.out.print(adjacentVertex + " ");
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex(5);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        System.out.println(graph.isConnected());
        graph.DFS(1);
        System.out.println();
        graph.printGraph();
        graph.removeVertex(5);
        System.out.println();
        graph.printGraph();
    }
};        

Here is an example of several Graph Methods using ArrayList and HashMap.

Steps:

1. Define a Graph class that will represent the graph structure.
2. Create a HashMap to store the vertices and their corresponding adjacent vertices. The key of the HashMap will be the vertex and the value will be an ArrayList of adjacent vertices.
3. Define a method to add a vertex to the graph. In this method, you will create a new entry in the HashMap with an empty ArrayList for the adjacent vertices.
4. Define a method to add an edge between two vertices. In this method, you will add the second vertex to the ArrayList of adjacent vertices for the first vertex in the HashMap.
5. Define a method to get the adjacent vertices for a given vertex. In this method, you will return the ArrayList of adjacent vertices for the given vertex in the HashMap.
6. Define more methods like removeVertices, removeEdges, isConnected, and DFS. These methods are very much essential to manipulate a Graph.
7. Define a method to print the graph. In this method, you will iterate through the HashMap and print out each vertex and its adjacent vertices.

#datastructures

#graph