Graph Data Structure
In this article, you will learn about Graph data structure types, representations, implementations and algorithms
A graph is a data structure used for organizing an interconnected network. It is a nonlinear data structure consisting of a collection of vertices (nodes) and edges
 A vertex represents an entity (object) (for example, student)
 An edge is a line or arc that connects a pair of vertices in the graph, represents the relationship between entities
Examples
 A computer network is a graph with computers are vertices and network connections between them are edges
 The World Wide Web is a graph with web pages are vertices and hyperlinks are edges
Types of Graphs
Undirected vs Directed graph
 An undirected graph has all edges that don’t have a direction, each edge can be travel in both directions (twoway relationships)
 A directed graph has all edges that have a direction, each edge can be travel only in a single direction (oneway relationship)
Cyclic vs Acyclic graph
 A cyclic graph has at least a cycle (existing a path from at least one node back to itself)
 An acyclic graph has no cycles
Connected vs Disconnected graph
 A connected graph has no unreachable vertices (existing a path between every pair of vertices)
 A disconnected graph has at least an unreachable vertex
Tree vs Forrest
 A tree is a connected acyclic undirected graph
 A forest is a graph with each connected component a tree
Weighted vs Unweighted graph
 A weighted graph has a weight attached to each edge (for example, the distance between two vertices)
 An unweighted graph has no weight attached to each edge
Vertex and Graph degree
Verex degree, denoted as deg(v), is a number of edges connected to the vertex. Graph degree, denoted as Δ(G), is the highest vertex degree in a graph
In the above graph
 deg(0) = 2, deg(1) = 2, deg(2) = 3, and deg(3) = 1
 Δ(G) = 3
Vertex Indegree vs Outdegree
In a directed graph, vertex has an indegree and outdegree
 An indegree, denoted as
deg+(v)
, is a number of edges coming to the vertex  An outdegree, denoted as
deg(v)
, is a number of edges leaving the vertex
In the above graph
 deg+(0) = 1, deg(0) = 1
 deg+(1) = 2, deg(1) = 0
 deg+(2) = 1, deg(2) = 2
 deg+(3) = 0, deg(3) = 1
Graph Representations
There are several ways to represent a graph including the Edge list, Adjacency list, and Adjacency matrix. Let take this graph as an example

An edge list is a list or array of all edges where each edge is represented by an array of two vertices
In Java, an edge list can be represented by
int[][] graph = {
{0, 1},
{0, 2},
{1, 2},
{2, 3}
};

An adjacency list is a list or array where index represents a vertex and value represents a list of that vertex’s adjacents
In Java, an adjacency list can be represented by
int[][] graph = {
{1, 2},
{0, 2},
{0, 1, 3},
{2}
};

An adjacency matrix is a matrix of 0s and 1s indicating the connection between two vertices in which the rows represent source vertices and columns represent destination vertices
In Java, an adjacency matrix can be represented by
int[][] graph = {
{0, 1, 1, 0},
{1, 0, 1, 0},
{1, 1, 0, 1},
{0, 0, 1, 0}
};
Basic Graph operations
 Add edge: add an edge between two vertices of the graph
 Traversal: travel each vertex in the graph by using DepthFrist and BreathFirst Search
Graphs in Java
Java doesn’t have a default Graph implementation. However, you can use other supporting data structures to implement it
Undirected vs Directed Graph implementation example
 Undirected graph implementation example with an adjacency list
GraphUndirectedByAdjacencyList.java
package com.hellokoding.datastructure.graph;
import java.util.ArrayList;
import java.util.List;
public class GraphUndirectedByAdjacencyList {
private int V;
private List<List<Integer>> adjacencyList;
public GraphUndirectedByAdjacencyList(int V) {
this.V = V;
adjacencyList = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adjacencyList.add(new ArrayList<>());
}
}
public Integer getV() {
return this.V;
}
public List<List<Integer>> getAdjacencyList() {
return this.adjacencyList;
}
public void addEdge(int source, int dest) {
adjacencyList.get(source).add(dest);
adjacencyList.get(dest).add(source);
}
public void printAdjacencyList() {
for (int i = 0; i < V; i++) {
System.out.printf("Adjacency list of vertex %d is %s %s", i,
adjacencyList.get(i), System.lineSeparator());
}
}
public static void main(String[] args) {
GraphUndirectedByAdjacencyList graph = new GraphUndirectedByAdjacencyList(3);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.printAdjacencyList();
}
}
 Directed graph implementation example with an adjacency list
GraphDirectedByAdjacencyList.java
package com.hellokoding.datastructure.graph;
import java.util.ArrayList;
import java.util.List;
public class GraphDirectedByAdjacencyList {
private int V;
private List<List<Integer>> adjacencyList;
public GraphDirectedByAdjacencyList(int V) {
this.V = V;
adjacencyList = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adjacencyList.add(new ArrayList<>());
}
}
public Integer getV() {
return this.V;
}
public List<List<Integer>> getAdjacencyList() {
return this.adjacencyList;
}
public void addEdge(int source, int dest) {
adjacencyList.get(source).add(dest);
}
public void printAdjacencyList() {
for (int i = 0; i < V; i++) {
System.out.printf("Adjacency list of vertex %d is %s %s", i,
adjacencyList.get(i), System.lineSeparator());
}
}
public static void main(String[] args) {
GraphDirectedByAdjacencyList graph = new GraphDirectedByAdjacencyList(3);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.printAdjacencyList();
}
}
 The only difference between the implementations is the
addEdge(source, dest)
method.addEdge
in an undirected graph adds twoways direction while in a directed graph adds oneway direction
// addEdge in a directed graph
public void addEdge(int source, int dest) {
adjacencyList[source].add(dest);
}
// addEdge in an undirected graph
public void addEdge(int source, int dest) {
adjacencyList[source].add(dest);
adjacencyList[dest].add(source);
}
Weighted Graph implementation example
 Weighted graph implementation example with an adjacency list
GraphWeightedByAdjacencyList.java
package com.hellokoding.datastructure.graph;
import java.util.ArrayList;
import java.util.List;
public class GraphWeightedByAdjacencyList {
private int V;
private List<List<WeightedVertex>> adjacencyList;
public GraphWeightedByAdjacencyList(int V) {
this.V = V;
adjacencyList = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adjacencyList.add(new ArrayList<>());
}
}
public Integer getV() {
return this.V;
}
public List<List<WeightedVertex>> getAdjacencyList() {
return this.adjacencyList;
}
public void addEdge(int source, int dest, int weight) {
adjacencyList.get(source).add(new WeightedVertex(dest, weight));
}
public void printAdjacencyList() {
for (int i = 0; i < V; i++) {
System.out.printf("Adjacency list of vertex %d is %s %s", i,
adjacencyList.get(i), System.lineSeparator());
}
}
static class WeightedVertex {
final Integer vertex, weight;
public WeightedVertex(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
public int getWeight() {
return this.weight;
}
public String toString() {
return String.format("%d (weight %d)", vertex, weight);
}
}
public static void main(String[] args) {
GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
g.addEdge(0, 1, 19);
g.addEdge(2, 0, 15);
g.addEdge(2, 1, 17);
g.addEdge(3, 2, 12);
g.printAdjacencyList();
}
}
Graph traversal and searching with DepthFirst and BreadthFirst Search
DepthFirst Search (DFS) and BreadthFirst Search (BFS) are algorithms for traversing or searching a graph

DFS starts at an arbitrary node and explores as far as possible along each branch before backtracking
BFS starts at an arbitrary node and explores all of the neighbor nodes at the current level before moving on to the next level
Thus DFS is better when the target is far from the source while BFS is better when the target is close to the source
 DFS uses a Stack while BFS uses a Queue data structure to backtrack vertices on the traversal path
 DFS consumes less memory than BFS as BFS has to store all the children each level
Learn more about DepthFirst Search and BreadthFirst Search
Detect Cycle in a Directed Graph
You can use DFS to detect a cycle in a directed graph. When visiting a vertex v and its adjacency vertices, if there is a back edge (w, v) which directs to v then that graph has a cycle
Topological Sort with Directed Acyclic Graph
Topological sort is an algorithm which takes a directed acyclic graph and returns a list of vertices in the linear ordering where each vertex has to precede all vertices it directs to
DFS and the above vertex degree theory can be used to implement the topological sort
Find shortest paths between vertices
The shortest path is a path between two vertices in a graph such that the total sum of the weights of the constituent edges is minimum
You can implement an algorithm to find the shortest path by using BreadthFirst Search (BFS), Dijkstra, BellmanFord, and FloydWarshall algorithms