# Graph Fundamentals in Java

By Arvind Pandey
Published in Programming
May 14, 2020

#### What is a Graph?

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.

#### Graph Terminologies

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.

#### How to represent the Graph?

There are different ways to represent graph. Two are most popular one.

#### Adjacency List representation of the Graph

In this representaion, you store the adjacent vertext as list.

#### Adjacency Matrix representation of the Graph

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.

#### Which representation is better?

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.

#### Graph Implementation - 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) {
}

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"};
graph.printGraph();
}
}
```

Console Output

```Delhi-->Hyderabad-->Bangalore-->Mumbai-->Chennai-->Guwahati
Chennai-->Bangalore-->Delhi-->Mumbai
Bangalore-->Chennai-->Mumbai-->Delhi
```

Hope you liked this tutorial. You might also like other tutorials in this series here

## Tags

#ds#programming#java
Previous Article
HashMap Fundamentals in Java

## Topics

Life & Productivity
Programming
Running

## Related Posts

Build Rest API from scratch in Node.js
July 24, 2020
4 min