Today, you will study how to implement Graph Adjacency List in Java. It’s easy for you to understand if you have basic knowledge about Graph data structure, but you don’t, please refer to the post Graph Data Structure in Java. Now, let’s find out what we study today.
Implement Graph Adjacency List in Java
Adjacency List representation
You know, an adjacency list represents a graph as an array of linked list. Each specified index of the array represents a vertex and each element in its linked list represents the other vertices that have an edge with that vertex. Here is a graph and its adjacency list representation is shown below.
Have a look at that above image. An array of lists is used. Size of the array is equal to the number of vertices. Suppose that the array is array[]. An entry array[i] represents the list of vertices adjacent to the i th vertex. This representation can also be used to represent a weighted graph.
Pros and Cons
This representation is better space efficiency because it only stores the values for the edges, so it saves spaces O(|V|+|E|). But it is comparatively difficult to implement and less efficient to query. For example, a query whether there is an edge from a vertex to another vertex is not efficient and can be done O(V).
Adjacency List impelementation
We can use Java collection to implement graph adjacency list in Java. Here we use a map to store an array of linked list. The map’s keys are equivalent to vertices then each map’s value is used to store a linked list of other adjacency vertices. Actually, I prefer to use a map than an array with indexes because I can implement any type of vertex object like a number, string, object, etc.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
// Simple program implements a Graph in adjacency list import java.util.*; class Graph { // We use Hashmap to store the edges in the graph // Hashmap keys are the vertices and values are the edges private Map<Integer, List<Integer>> map = new HashMap<>(); // adds a new vertex to the graph public void addVertex(Integer vertex) { map.put(vertex, new LinkedList<Integer>()); } // adds the edge of source and destination vertexs public void addEdge(Integer sVertex, Integer dVertex) { if (!map.containsKey(sVertex)) addVertex(sVertex); if (!map.containsKey(dVertex)) addVertex(dVertex); map.get(sVertex).add(dVertex); } // get graph size public Integer size() { return map.keySet().size(); } // return the count of edges public Integer getEdgesCount() { int count = 0; for (Integer v : map.keySet()) { count += map.get(v).size(); } return count; } // graph contains a vertex or not. public boolean containsVertex(Integer vertex) { return map.containsKey(vertex)?true:false; } // an edge of two vertices is present or not. public boolean existEdge(Integer sVertex, Integer dVertex) { return map.get(sVertex).contains(dVertex)?true:false; } // Displays the adjancency list of each vertex. @Override public String toString() { StringBuilder builder = new StringBuilder(); for (Integer vertex : map.keySet()) { builder.append(vertex.toString() + ": "); for (Integer dVertex : map.get(vertex)) { builder.append(dVertex.toString() + " "); } builder.append("\n"); } return (builder.toString()); } } // Main class public class Main { public static void main(String args[]) { // create new graph instance Graph g = new Graph(); // edges are added. g.addEdge(10, 20); g.addEdge(10, 40); g.addEdge(20, 10); g.addEdge(20, 30); g.addEdge(20, 40); g.addEdge(30, 20); g.addEdge(30, 40); g.addEdge(40, 10); g.addEdge(40, 20); g.addEdge(40, 30); // print the graph. System.out.println("Here is the graph:\n" + g.toString()); // print number of vertices in the graph. System.out.println("Number of vertices graph: "+g.size()); // print number of edges in the graph. System.out.println("Number of edges graph: "+g.getEdgesCount()); // check a vertex exists or not System.out.print("Vertex 40 exists? "); System.out.println(g.containsVertex(40)?"YES":"NO"); //check a edges exists or not System.out.print("Vertex 40 and 20 exists an edges? "); System.out.println(g.existEdge(20,40)?"YES":"NO"); } } |
Running the above program, you will get the output like below
That’s all about Implement Graph Adjacency List in Java.
