Graph is one of the data structures in computer programming. Below is a sample airport route between cities. Bi-directional arrow indicates that flights fly both way.
Say, we need a data structure to represent such scenario. Then graph data structure is the one that comes to the rescue. Or one another example of graph data structure is social networks, i.e facebook.
Vertex(V): Each end-point is called vertex. Like cities are vertices here.
Edge(E): The line that connects two vertices is called edge.
Graph(G): The complete arrangement is called Graph.
There are different ways to represent graph. Two are most popular one.
In this representaion, you store the adjacent vertext as list.
In this representation, each vertex is represented as index of a 2-d array of size V*V. Where is V is the total number of vertices. If there is connection between vertices, then you store 1 at the corresponding coordinate, if not then you store 0. Here 0 means Delhi and 1 means Mumbai. The coordinate (0,0) means, connection between Delhi and Delhi. That has to be true, each vertex is reachable to its own. So it stores value 1. The coordinate (0,1) means connection between Delhi and Mumbai. Similarly the coordinate (1, 0) means connection between Mumbai and Delhi.
Notice: If all the edges are bi-directional then resulting matirx would be a symmetric matrix.
That’s quite debatable. If the resulting matrix is sparse matrix then you will end up storing a lot of 0’s in the matrix, for that matter you do not care much about them. You care more about what’s connected. In that case adjacency list is better. But, in another case, if the connectivity is dense and you expect all the vertices are mostly connected then adjacency matrix is better than adjacency list.
For our illustration, we will use adjacency list.
import java.util.ArrayList; import java.util.HashMap; public class AdjacencyGraph { private HashMap<String, ArrayList<String>> graph= new HashMap<>(); public AdjacencyGraph(String[] arr) { for(int i=0; i<arr.length; i++) { graph.put(arr[i], new ArrayList<>()); } } // Assuming bi-directional graph public void add(String src, String dst) { graph.get(src).add(dst); graph.get(dst).add(src); } public void printGraph() { for(String s: graph.keySet()) { ArrayList<String> a = graph.get(s); System.out.print(s+"-->"); for(int k=0;k<a.size();k++) { if(k == a.size()-1) { System.out.print(a.get(k)); } else { System.out.print(a.get(k)+"-->"); } } System.out.println(); } } public static void main(String[] args) { String[] arr = {"Hyderabad", "Delhi", "Bangalore", "Chennai", "Mumbai", "Guwahati"}; AdjacencyGraph graph = new AdjacencyGraph(arr); graph.add("Hyderabad","Mumbai"); graph.add("Hyderabad","Delhi"); graph.add("Hyderabad","Guwahati"); graph.add("Bangalore","Chennai"); graph.add("Bangalore","Mumbai"); graph.add("Bangalore","Delhi"); graph.add("Delhi","Mumbai"); graph.add("Delhi","Chennai"); graph.add("Delhi","Guwahati"); graph.add("Mumbai","Chennai"); graph.printGraph(); } }
Console Output
Delhi-->Hyderabad-->Bangalore-->Mumbai-->Chennai-->Guwahati Guwahati-->Hyderabad-->Delhi Chennai-->Bangalore-->Delhi-->Mumbai Mumbai-->Hyderabad-->Bangalore-->Delhi-->Chennai Hyderabad-->Mumbai-->Delhi-->Guwahati Bangalore-->Chennai-->Mumbai-->Delhi
Hope you liked this tutorial. You might also like other tutorials in this series here
Quick Links
Legal Stuff