Introduction to Graph Algorithms and Implementation

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

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

What is a graph?

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 these otherwise difficult problems.

Representing graphs

Graphs represent pairwise relationships between objects. Graphs are mathematical structures and, therefore, can be visualized by using 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. A relationship between nodes is expressed using edges. An edge between two nodes expresses the relationship between the nodes.

Graphs can be represented as an adjacency matrix or adjacency list.

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

Adjacency list

An adjacency list is used to represent a finite graph. The adjacency list representation allows us to iterate through the neighbors of a node easily. Each index in the list represents the vertex and each node that is linked with that index represents its neighboring vertices.

Adjacency matrix

An adjacency matrix is a square matrix labeled by graph vertices and is used to represent a finite graph. The entries of the matrix indicate whether the vertex pair is adjacent or not in the graph.

In the adjacency matrix representation, we will need to iterate through all the nodes to identify a node’s neighbors.

Types of graphs

There can be two types of graphs in terms of structure:

• Directed graph: The directed graph is the one in which all edges are directed from one vertex to another.

• Undirected graph: The undirected graph is the one in which all edges are not directed from one vertex to another.

Mathematical notation

The set of vertices of graph $G$ is denoted by $V(G)$, or just $V$ ...