Introduction to Graph Algorithms and Implementation

In this lesson, you will learn about graphs and how to represent them.

We'll cover the following

Introduction to graphs

In this chapter, you will be studying graph algorithms. These algorithms use the basic graph structure.

Before we begin, let’s briefly discuss what graphs are?

A graph is an abstract notation used to represent the connection between pairs of objects. It can be used to represent networks: systems of roads, airline flights from city to city, how the Internet is connected, or social connectivity on facebook, twitter etc. We use some standard graph algorithms to solve otherwise difficult problems in these domains.

Representing graphs

Graphs represent pairwise relationships between objects. Graphs are mathematical structures and consist of two basic components; nodes and edges.

A node, also known as a vertex, is a fundamental part of a graph. It is the entity that has a name, known as the key, and other information related to that entity. The relationship between nodes is expressed using edges. An edge between two nodes expresses a one-way or two-way relationship between the nodes. In general, there can be more than one edge between a given pair of vertices called parallel edges, and there can be an edge from a vertex to itself, called self loop.

Graphs can be represented as adjacency matrix and adjacency list.

Adjacency matrix and adjacency list of the same graph
Adjacency matrix and adjacency list of the same graph

For the remainder of this course, we will be using adjacency lists because algorithms can be performed more efficiently using this form of representation.

For example, the adjacency list representation allows you to easily iterate through the neighbors of a node. In the adjacency matrix representation, you need to iterate through all the nodes to identify a node’s neighbors.

Mathematical notation

The set of vertices of Graph GG is denoted by V(G)V(G), or just VV if there is no ambiguity.

An edge between vertices uu and vv is written as u,v{u, v}. The set of edges of GG is denoted E(G)E(G), or just EE if there is no ambiguity.

The graph in this picture has the vertex set VV = {1, 2, 3, 4, 5, 6}.

The edge set EE = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}.

Undirected graph
Undirected graph

A path in a graph GG == (V,E)(V, E) is a sequence of vertices v1,v2,…,vkv1, v2, …, vk, with the property that there are edges between vivi and vi+1vi+1. We say that the path goes from v1v1 to vkvk. In the graph above, the sequence 6,4,5,1,26, 4, 5, 1, 2 is a path from node 66 to node 22. A path is simple if its vertices are all different.

A cycle is a path v1,v2,…,vkv1, v2, …, vk for which k>2k > 2, and the first k−1k - 1 vertices are all different

  1. v1=vkv1 = vk

The sequence 4,5,2,3,44, 5, 2, 3, 4 is a cycle in the graph above.

A graph is connected if for every pair of vertices uu and vv, there is a path from uu to vv.

The graph class

The graph class consists of two data members:

  • The total number of vertices in the graph
  • A list of linked lists to store adjacent vertices

So let’s get down to the implementation!

Press + to interact
class Graph {
 private int vertices; //number of vertices 
 private LinkedList < Integer > adjacencyList[]; //Adjacency Lists 
 @SuppressWarnings("unchecked")
 // Constructor 
 public Graph(int vertices) {
  vertices = vertices;
  adjacencyList = new LinkedList[vertices];
  for (int i = 0; i < vertices; ++i)
   adjacencyList[i] = new LinkedList();
 }
 // Function to add an edge into the graph 
 void addEdge(int source, int destination) {
  adjacencyList[source].add(destination);
 }
 public int getVertices() {
  return this.vertices;
 }
 public LinkedList < Integer > [] getAdj() {
  return this.adjacencyList;
 }
}
class Main {
 public static void main(String args[]) {
  Graph g = new Graph(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 3);
  g.addEdge(3, 0);
 }
}

We’ve laid down the foundation of our Graph class. The variable vertices contains an integer specifying the total number of vertices.

The second component is an ArrayList of integers called adjacencyList, which, when the graph constructor is called, is assigned memory according to the number of nodes we want to create. We simply have to run a loop and create a list for each vertex V.