Graph - Introduction

In this post, I would like to give a simple description about a data structure - graph. There are several useful algorithms on graph and I will talk about them later.

Firstly, what is a graph?

The following two figures shows two simple graphs.

Graph 1

Graph 2

You may notice the difference between the above two graphs. Let's see the formally definition.

Graph
A graph G = (V, E) consist of a finite set of vertices (or nodes) V= {\(v_1\), \(v_2\), ..., \(v_n\)} and a set of edges E. The graph 1 in above figures is called undirected graph and each edge in its E is an unordered pair of vertices. The graph 2 is called directed graph and each edge in its E is an ordered pair of vertices.

An undirected graph is said to be complete if there is an edge between each pair of its vertices. A directed graph is said to be complete if there is an edge from each vertex to all other vertices.

Are the above two graphs complete? Yes to the undirected graph and no to the directed graph.

Representation of graphs

There are two commonly used data structures to represent a graph.

Adjacency matrix 
Adjacency matrix M of a graph G is a boolean matrix which M[i, j] = 1 if and only if (\(v_i, v_j\)) is an edge in G.

Adjacency list
Adjacency list is a collection of linked list, each list represent the vertices adjacent to 
a vertex.

The figures below show two representations of an undirected graph and a directed graph.

Undirected graph 

Directed graph

A JAVA implementation of the above graphs can be found on GitHub - Adjacency Matrix and Adjacency List.