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.

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 $G$ is denoted by $V(G)$, or just $V$ if there is no ambiguity.

An edge between vertices $u$ and $v$ is written as ...