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.
