Prerequisite: Generic Class
We can also use them to code for Graph in Java. The Graph class is implemented using HashMap in Java. As we know HashMap contains a key and a value, we represent nodes as keys and their adjacency list in values in the graph.
Illustration: An undirected and unweighted graph with 5 vertices.
Adjacency Matrix is as follows:
Adjacency List is as follows:
Approach:
Just unlikely in C++, we use <> to specify parameter types in generic class creation.
Syntax: To create objects of a generic class
BaseType <Type> obj = new BaseType <Type>()
Note: In Parameter type, we cannot use primitives like ‘int’, ‘char’, or ‘double’.
Example
Java
// Java program to implement Graph// with the help of Genericsimport java.util.*;class Graph<T> { // We use Hashmap to store the edges in the graph private Map<T, List<T> > map = new HashMap<>(); // This function adds a new vertex to the graph public void addVertex(T s) { map.put(s, new LinkedList<T>()); } // This function adds the edge // between source to destination public void addEdge(T source, T destination, boolean bidirectional) { if (!map.containsKey(source)) addVertex(source); if (!map.containsKey(destination)) addVertex(destination); map.get(source).add(destination); if (bidirectional == true) { map.get(destination).add(source); } } // This function gives the count of vertices public void getVertexCount() { System.out.println("The graph has " + map.keySet().size() + " vertex"); } // This function gives the count of edges public void getEdgesCount(boolean bidirection) { int count = 0; for (T v : map.keySet()) { count += map.get(v).size(); } if (bidirection == true) { count = count / 2; } System.out.println("The graph has " + count + " edges."); } // This function gives whether // a vertex is present or not. public void hasVertex(T s) { if (map.containsKey(s)) { System.out.println("The graph contains " + s + " as a vertex."); } else { System.out.println("The graph does not contain " + s + " as a vertex."); } } // This function gives whether an edge is present or not. public void hasEdge(T s, T d) { if (map.get(s).contains(d)) { System.out.println("The graph has an edge between " + s + " and " + d + "."); } else { System.out.println("The graph has no edge between " + s + " and " + d + "."); } } // Prints the adjancency list of each vertex. @Override public String toString() { StringBuilder builder = new StringBuilder(); for (T v : map.keySet()) { builder.append(v.toString() + ": "); for (T w : map.get(v)) { builder.append(w.toString() + " "); } builder.append("\n"); } return (builder.toString()); }}// Driver Codepublic class Main { public static void main(String args[]) { // Object of graph is created. Graph<Integer> g = new Graph<Integer>(); // edges are added. // Since the graph is bidirectional, // so boolean bidirectional is passed as true. g.addEdge(0, 1, true); g.addEdge(0, 4, true); g.addEdge(1, 2, true); g.addEdge(1, 3, true); g.addEdge(1, 4, true); g.addEdge(2, 3, true); g.addEdge(3, 4, true); // Printing the graph System.out.println("Graph:\n" + g.toString()); // Gives the no of vertices in the graph. g.getVertexCount(); // Gives the no of edges in the graph. g.getEdgesCount(true); // Tells whether the edge is present or not. g.hasEdge(3, 4); // Tells whether vertex is present or not g.hasVertex(5); }} |
Output:
Graph: 0: 1 4 1: 0 2 3 4 2: 1 3 3: 1 2 4 4: 0 1 3 The graph has 5 vertex The graph has 7 edges. The graph has an edge between 3 and 4. The graph does not contain 5 as a vertex.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
