A graph can be represented in many ways. But we'll look into two of most popular methods of representing a graph.

This is a simple method of representing a graph. Let's consider a graph,

where V is the set of all vertices and E is the set of all edges. The Adjacency Matrix of this graph is structured as a 2-D matrix of the dimensions V x V. Each element in this matrix represents the existence of an edge in the graph. Formally, for an undirected unweighted graph,

For a directed unweighted graph, the adjacency matrix is a little different. Since the directions matter now, the notation will be,

That is A<sub>ij</sub> will be 1 only when there is an edge from i to j but not if there is an edge from j to i.

Notice that all the values are 1 because we defined them for unweighted graphs. The definition for Undirected Weighted Graphs will be,

Let's look at some examples for graphs,
The first graph is an undirected unweighted graph and the second one is a directed unweighted graph.

The above graph is a weighted undirected graph.

An Adjacency list is a collection of unordered lists with each list containing the neighbours of the corresponding vertex. For example, consider the following undirected and unweighted graph,

The adjacency list for this graph will be,
a -> {b,c} b -> {a,c} c -> {b,a}
In case of a directed unwieghted graph, only the vertex with outgoing edge has the vertex with edges as incoming in it's list. The following diagram shows both the adjacency matrix as well as list for the graph shown.

When we create an adjacency list for a weighted graph, we need to keep track of the weights as well. In C++, this is generally done by using pairs of integers and these pairs are stored in the adjacency lists.

In the next tutorial, we'll look into the first of many graph algorithms.