Graph Data Structure - Explained With Examples

Data structures are specialized formats that we use to store, process, and retrieve data according to our needs. There are several data structures that serve different purposes depending on the requirements; like the different types of utensils in our kitchen.

For example- We use bowls or cups for storing liquid items, plates won’t work in that case.

Similarly, in some cases, we need an array data structure, in some cases we need linked lists, and in some certain cases we need graphs.

Before we zone in on graph data structure, here are a few things we've covered earlier, in case you might want to learn:

Data Structures & Algorithms

Array Data Structure

Stack Data Structure

Queue Data Structure

Linked List Data Structure

Table of Contents

Graph Terminology

Basic Operations in a Graph

Types of Graphs

Graph Representation

Applications of Graphs

Introduction to Graph

A graph is non-linear data structure. It is a collection of nodes connected to each other by edges. Each node contains a data field.

Let's understand this with an example-

On Facebook, every profile is a node, including photos, videos, events, pages, and all other properties that have data.

And every connection acts as an edge, whether it’s between you and your Facebook friend or just a page you’ve liked.

Facebook and other social networks are just huge collections of nodes and edges.

Graph data structure solves many real-life problems. Most importantly they’re used to represent networks such as road networks in a city or circuit networks among other things.

A graph consists of-

• A collection of nodes also known as vertices, in this case
• A collection of edges E connecting the vertices, (represented as ordered pair of vertices- 0, 1)

V (Vertices) = {0, 1, 2, 3}

E (Edges) = {(0,1), (0,2), (0,3), (1,2)}

G (Graph) = {V, E}

Graph terminology

Vertex - Each node of a graph is called a vertex. (plural - vertices). In the image above, the dots represented by 0, 1, 2, and 3 are vertices.

Edge - Edges in a graph are the lines that connect two vertices. In the image above- the line (0, 1) from 0 to 1 represents an edge, similarly (1, 2), and so on.

Edges can be represented in the form of two-dimensional arrays.

Adjacency - A vertex is adjacent to another vertex if there is an edge connecting them. In the image above, vertices 0 and 1 are adjacent, but vertices 1 and 3 are not adjacent as there’s no edge between them.

Paths - A series of edges that takes you from one vertex to another when they’re not adjacent to each other. In the above example: 1 and 3 are not adjacent. So, the sequence of edges [(1, 2), (2, 3)] will represent a path.

Directed Graph - A graph in which an edge (0, 1) doesn't necessarily mean that there is an edge (1, 0) as well. An edge in a directed graph travels in only one direction. Arrows are used to represent that direction. (More on directed graphs later in the article)

Basic Operations in a Graph

Add/Remove Vertex

This is the most basic operation in a graph. You have to simply add a vertex to the graph; not needing to connect it with some other vertex through an edge.

While removing a vertex, you have to delete all the edges to and from that particular vertex.

Add/Remove Edge

This operation adds or removes an edge between two vertices. If all the edges originating from or ending at say vertex 1 is removed, 1 would become isolated.

Breadth-First Search

This search operation traverses all the nodes at a single level/hierarchy before moving on to the next level of nodes. BFS algorithm starts at the first node (in this picture - 1) and traverses all the nodes adjacent to 1 i.e. 2 and 3. After all the nodes at the first level are traversed, it proceeds to the next level repeating the same process.

For example - After vertices 2 and 3 are traversed, the BFS algorithm will then move to the first adjacent node of 2 i.e. 4, and traverse all its adjacent nodes. This goes on until all the nodes in the graph are searched.

Depth-First Search

This algorithm traverses the nodes in a vertical fashion. It starts with the root node and traverses one adjacent node and all its child nodes before moving on to the next adjacent node.

Example - The algorithm will start with 1 and search all the nodes connected to 2 - 4 and 5, and then move to the next adjacent node to 1 i.e. 3. The order would be given as: 1 -> 2 -> 4 -> 5 -> 3.

Types of Graphs

Finite Graph

A finite Graph has a defined (countable) number of vertices and edges.

If a graph G = (A, B) has a finite number of vertices A and edges B, it's a finite graph.

Infinite graph

As the name suggests, an infinite graph has an unlimited number of vertices and edges. It would still be represented as G = (A, B) but the values of both A and B would be infinite.

Trivial Graph

It's a graph with only one vertex, and therefore no edges.

Simple Graph

A simple Graph is one in which there is only one edge connecting a pair of vertices. (as shown in the image above). A railway track connecting two different cities is a perfect example of a simple Graph.

Multi Graph

You search for a location in Google maps and it shows multiple paths taking you to the same location. That's a multi Graph in which more than one edge could be connecting two vertices.

Null Graph

In a null graph, no edges are there to connect the vertices, meaning, all the vertices are isolated.

Null graphs have a zero size.

Order in a graph - Number of vertices

Size - Number of edges

So, a null graph might have 'n' order but will be of 'zero' size.

Complete Graph

In a complete graph, each vertex is adjacent to all of its vertices i.e. all the vertices in the graph are connected to each other.

Pseudo Graph

A pseudo Graph G = {A, B} contains a self-loop and multiple edges. In the above image, we have the vertices (1, 2, 3, 4) in which 1 and 2 have multiple edges between them and 2 also has a self-loop.

Regular Graph

It's a regular graph if every node of the graph is connected to the same number of vertices.

Example: In a 2-regular Graph, each vertex is connected to two other vertices. Similarly, in a 3-regular graph, each vertex is adjacent to three other vertices.

Note: All complete graphs are regular graphs but all regular graphs are not necessarily complete graphs.

Bipartite Graph

This one is a bit complicated. In a bipartite graph, the vertices are divided into two subsets (Set A and Set B), and all the edges connect a node from Set A to a node from Set B.

No edge will be connecting two nodes in the same set.

Let's make it more clear -

If we take two sets as A = {1, 2, 3, 4} and B = {5, 6, 7} then the vertices of Set A will only be connected with the vertices of Set B.

Labelled Graph

A labelled graph is the one in which the vertices and edges of a graph have a name, data, or weight attached to them. It can also be termed a weighted graph, for obvious reasons.

Direct Graph

A direct graph has edges that connect to an ordered pair of vertices. If an edge is connecting a pair of vertices (1 and 2) from 1 to 2, the edge will have an arrow directed to 2. If we change the direction of the arrow, the meaning of the graph will change.

They are also known as Digraphs and are useful in marking hierarchies in social networks and roadways.

Connected & Disconnected Graphs

If any pair of vertices (a, b) of a graph are reachable from one another, it can be called a connected graph. In other words, there needs to be at least one path between each and every pair of vertices for it to be a connected graph.

A connected graph with x number of vertices will have at least x-1 edges.

If even one edge between any pair of vertices is missing, it becomes a disconnected graph.

A null graph with no edges will always be a disconnected graph.

Cyclic Graph

As the name suggests, the vertices and edges form a cycle in a cyclic graph. The number of vertices n in a cyclic graph will always be equal to or greater than 3 (n>=3), and the number of edges will also be 'n' for it to form a cycle.

Example - A graph G that consists of n vertices (n>=3) i.e. X1, X2, X3........Xn and edges (X1, X2), (X2, X3), (X3, X4)........(Xn, X1) will be a cyclic graph, since the last vertex Xn is also connected to X1.

Acyclic graph

If there are no cycles present in a graph, it's an acyclic graph. If we start traversing the graph from point 2, we wouldn't have a path to traverse all the vertices and come back to point 2.

Representation of Graph

Let's say that we have to store a graph in the computer's memory. What technique will we use?

How will we represent the graph?

There are two major ways to do that:

• Adjacency matrix (Sequential representation)
• Adjacency list (Linked list representation)

We'll cover both of them one by one.

Adjacency matrix

An adjacency matrix is used to represent the mapping between vertices and edges of the graph. It can represent the undirected graph, directed graph, weighted undirected, and weighted directed graph. How?

Let's understand this with an undirected graph-

If there are n vertices in an undirected graph, the adjacency matrix for that graph will be n*n.

And each matrix will be denoted by either O or 1 depending upon the existence of the edge between two nodes.

So, any matrix adj[a][b] will denote the edges between vertex a and vertex b.

This matrix will be 1 if there exists an edge between the two nodes, else it will be 0.

• Xab = 1 (if there is a path between a to b)
• Xab = 0 (if not a single path exists between the two vertices)

If there is no self-loop present in the graph, the diagonal matrices will be 0.

The image shows the mapping among the vertices (a, b, c, d, e).

You'll find that the cross between a and a, or b and b says 0, that means there's no self loop.

Also, the cross between A*B and B*A says 1, which means it's an undirected graph

Activity: Match the binary values in the adjacency matrix with the edges in the graph. If the matrix for a particular pair says 0; there is no edge between the pair.

The adjacency matrix for a directed graph is different. The entry for Xab will be 1 only when there is an edge from vertex a to vertex b.

(Learn more about adjacency matrix representation here)

Adjacency list

Adjacency list uses linked lists to represent a graph. For each node in a graph, there exists a linked list that stores the node value and a pointer to the next adjacent node.

In the image, we can see that there is a linked list for every node in the graph. Vertex a is connected to both vertex b , and vertex d, as you can see in the adjacency list representing the graph.

Java implementation of graphs

Let's create a Java program to implement a graph-

import java.util.*;   
class Graph<T>   
{   
//creating an object of the Map class that stores the edges of the graph  
private Map<T, List<T> > map = new HashMap<>();   
//the method adds a new vertex to the graph  
public void addNewVertex(T s)   
{   
map.put(s, new LinkedList<T>());   
}   
//the method adds an edge between source and destination   
public void addNewEdge(T source, T destination, boolean bidirectional)   
{   
//      
if (!map.containsKey(source))   
addNewVertex(source);   
if (!map.containsKey(destination))   
addNewVertex(destination);   
map.get(source).add(destination);   
if (bidirectional == true)   
{   
map.get(destination).add(source);   
}   
}   
//the method counts the number of vertices  
public void countVertices()   
{   
System.out.println("Total number of vertices: "+ map.keySet().size());   
}   
//the method counts the number of edges  
public void countEdges(boolean bidirection)   
{   
//variable to store number of edges      
int count = 0;   
for (T v : map.keySet())   
{   
count = count + map.get(v).size();   
}   
if (bidirection == true)   
{   
count = count / 2;   
}   
System.out.println("Total number of edges: "+ count);   
}   
//checks a graph has vertex or not  
public void containsVertex(T s)   
{   
if (map.containsKey(s))   
{   
System.out.println("The graph contains "+ s + " as a vertex.");   
}   
else   
{   
System.out.println("The graph does not contain "+ s + " as a vertex.");   
}   
}   
//checks a graph has edge or not  
//where s and d are the two parameters that represent source(vertex) and destination (vertex)  
public void containsEdge(T s, T d)   
{   
if (map.get(s).contains(d))   
{   
System.out.println("The graph has an edge between "+ s + " and " + d + ".");   
}   
else   
{   
System.out.println("There is no edge between "+ s + " and " + d + ".");   
}   
}   
//prints the adjacencyS list of each vertex  
//here we have overridden the toString() method of the StringBuilder class  
@Override  
public String toString()   
{   
StringBuilder builder = new StringBuilder();   
//foreach loop that iterates over the keys  
for (T v : map.keySet())   
{   
builder.append(v.toString() + ": ");   
//foreach loop for getting the vertices  
for (T w : map.get(v))   
{   
builder.append(w.toString() + " ");   
}   
builder.append("\n");   
}   
return (builder.toString());   
}   
}   
//creating a class in which we have implemented the driver code  
public class GraphImplementation  
{   
public static void main(String args[])   
{   
//creating an object of the Graph class  
Graph graph=new Graph();  
//adding edges to the graph  
graph.addNewEdge(0, 1, true);   
graph.addNewEdge(0, 4, true);   
graph.addNewEdge(1, 2, true);   
graph.addNewEdge(1, 3, false);   
graph.addNewEdge(1, 4, true);   
graph.addNewEdge(2, 3, true);   
graph.addNewEdge(2, 4, true);   
graph.addNewEdge(3, 0, true);   
graph.addNewEdge(2, 0, true);   
//prints the adjacency matrix that represents the graph  
System.out.println("Adjacency List for the graph:\n"+ graph.toString());   
//counts the number of vertices in the graph   
graph.countVertices();   
//counts the number of edges in the graph   
graph.countEdges(true);   
//checks whether an edge is present or not between the two specified vertices  
graph.containsEdge(3, 4);   
graph.containsEdge(2, 4);   
//checks whether vertex is present or not   
graph.containsVertex(3);   
graph.containsVertex(5);   
}   
}  

Output:

Applications of Graph

Real-world applications

If you look closer, the whole wide universe could be a graph in itself. We can think of the universe at the very start as a collection of abstract relations between abstract elements. Some researchers do have explanations about this theory, and it only seems logical. (I’m attaching one of the researches here)

But let’s not go that deep for now, and look at some real-world applications of graph data structure that we can actually see and experience.

Social networks - This is one of the most basic applications of a graph. A social graph illustrates connections among people and organizations in a social network. Example: Facebook

Biological networks - Remember when we told you that the whole universe can be a graph? We were not lying. Our environment is also a huge graph that includes multiple hierarchies, brain networks, food chains, etc.

Web graph - World Wide Web is another huge graph data set where all the documents are connected to each other using hyperlinks. In this case, these hyperlinks can be considered edges.

Road networks/navigation - In the computer science world, all navigation problems are fittingly termed graph problems. In a huge city with hundreds of roads and alleys, graphs guide you from point A to point B.

You would have seen how the roads are connected in the form of vertices and edges on many modern apps like Google Maps, Uber, Maze, etc.

Not only that, but it also helps you find the shortest possible route.

Product recommendation - How do these e-commerce websites often know what you want, and recommend specific products?

Simple. They use the graph data structure to establish connections between what past users like you have bought.

Blockchains - One thing you must have heard of in recent years is blockchain technology. It is being deemed to be the future of all transactions.

In a distributed ledger, the blocks act as vertices and they’re all connected through edges. That’s how each user has the access to the required data and all transactions are transparent.

In Computer Science

• Graphs define the flow of computation. A control flow graph, originally developed by Frances E. Allen, acts as the graphical representation of computation during the execution of programs
• Graphs represent networks of communication.
  
• To represent data organization
• Operating systems use resource allocation graphs to understand the state of the system. Here, each resource and process are represented as vertices, and edges connect the resources to the allocated process.

Final thoughts

You just learned about the graph data structure, its types, and applications. We believe that learning data structures and algorithms are paramount to becoming a top-notch programmer.

In the words of Linus Torvalds, the main developer behind the Linux operating system:

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”

If you want to learn the core of data structures and algorithms, this article would be the perfect starting point.

However, if you’re serious about building a career in the tech industry as a developer, reading articles wouldn’t do the job. You need to train on every concept for hours, write thousands of lines of code, and solve DSA problems on a regular basis.

And this full-stack web development course by Masai will provide you with just that. Almost 1200 hours of practical training in web development where you’ll get to build websites, collaborate with teammates, face mock interviews, and much more. By the end of 30 weeks, you’ll be an industry-level developer ready to launch your career in top tech companies.

All of this at 0 upfront fee, as it’s a pay-after-placement program.

Students from all educational backgrounds have trained and gotten placed with high-end packages.

So, why not you?