The post introduces Graph Data Structure in Java, both concept and implementation. A graph data structure is a collection of nodes that are connected to other nodes. Every connection is an edge from one node to another. Let’s dig deeper.
Graph Data Structure in Java
Graph example
Now, you can try to discovery a bit about how Facebook uses graph data structure. On facebook, everything is a node. That might include User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note…anything that has data is a node. When you post a story, join group, like page etc., an edge is created for that connection. So Facebook uses graph data structure to store its data (nodes and edges).
In short, a Graph is a data structure that consists of:
- A collection of vertices V (also called nodes)
- A collection of edges E, which connect a pair of vertices.
The above graph may be described like this:
|
1 2 3 |
V = {10, 20, 30, 40} //collection of vertices E = {(10,20), (10,30), (10,40), (20,30), (30,40)}//collection of edges G = {V, E} |
Graph Terminology
- Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them. In the above graph, vertex 20 and 30 are adjacent because there is an edge between them. But vertex 20 and 40 are not adjacent as there is no edge between them.
- Path: A path is simply a collection of edges that allows you to go from a vertex to another vertex. In the above graph, paths of vertex 10 and vertex 40 are 10-20, 20-30, 30-40 and 10-40 .
- Directed Graph: A graph in which edges feature a direction so such a graph is known as a directed graph. The direction is represented by arrows to show the direction of the edge.
Graph Representation
A graph can be represented commonly in adjacency matrix and adjacency list. Each one has their pros and cons in a different set-up.
1. Adjacency Matrix
An adjacency matrix is 2D array of V x V vertices, with dimensions equivalent to the number of vertices in the graph. Each row and column represent a vertex. The elements of the adjacency matrix have values 0 or 1. A value 1 indicates an adjacency between the vertices and a value of 0 otherwise. The above graph can be represented in an adjacency matrix below
Let’s have a look on this adjacency matrix, you see 10 and 20 is adjacency but 10 and 30 otherwise. This representation is easier to implement and efficient to query as well. However, it requires more space because we must reserve space for every possible link between all vertices(V x V).
2. Adjacency List
In general, 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. The above graph might be represented in an adjacency list like below
This representation is comparatively difficult to implement and less efficient to query. But it is better space efficiency because it only stores the values for the edges.
Graph Operations
The most common graph operations are:
- Graph Traversal
- Check if element is present in graph
- Add elements(vertex, edges) to graph
- Finding path from one vertex to another vertex
Implement a Graph data structure in Java
I noticed that Java doesn’t have a default implementation of the graph data structure. But, you can implement a Graph Data Structure in Java using java collection to store its edges.
|
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 |
// 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; } // Displays the adjancency list of each vertex. @Override public String toString() { StringBuilder builder = new StringBuilder(); for (Integer v : map.keySet()) { builder.append(v.toString() + ": "); for (Integer w : map.get(v)) { builder.append(w.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(30, 20); g.addEdge(30, 40); g.addEdge(40, 10); 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()); } } |
Here is the output of the above program
That’s all about Graph Data Structure in Java. You might refer to the other data structures in Java
