An adjacency list represents a graph (or a tree) as an array of nodes that include their list of connections. Let’s first see how it looks like with a graph and its equivalent adjacency list representation:

The idea is pretty simple : the index of the array represents a node and each element in its list represents an outgoing connection with another node. Easy to create, easy to manipulate, here is how the data could be represented in JSON :

[
[1, 2, 3],
[0, 2],
[0, 1],
[0]
] 

Yes, it’s that simple! It includes all the information we need to go through and to visualize graphs or trees. This is for instance the data structure we choose to handle our mazes:

## Applications

The advantage of the adjacency list implementation is that it allows us to compactly represent a sparse graph. The adjacency list also allows us to easily find all the links that are directly connected to a particular node. It is used in places like: BFS, DFS, Dijkstra, A* (A-Star) etc.

Note: dense graphs are those which have a large number of edges and sparse graphs are those which have a small number of edges.

For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.
Perfect, we know everything to create and manipulate our graphs!
Build our own structures.
Understand graph traversal algorithms.

### What is next?

If you haven't jumped yet to maze generation algorithms, playing with them and using our explorer gives you visual insights of adjacency lists. We will soon study more graph data structures such as adjacency matrix which may be useful in particular cases.

To model this in C++, we can create a class called Node, which has two member variables:

- data: Any extra data you want to store
- neighbors: List of outgoing connections (using index as id)


struct Node
{
Node(const T& data, set< int > connections) : data(data), neighbors(connections) {}

T data;                // Any extra data you want to store
set< int > neighbors; // List of outgoing connections (using index)
};

class Graph
{
public:
Graph(vector< Node > nodes) : nodes(nodes);

private:
vector< Node > nodes; // All nodes contained in the graph
};



Let's create a bidirectional graph!


typedef Node< string > NodeT; // We choose to store the name's node

auto graph = Graph({
NodeT("Globo", {1, 2, 3}),
NodeT("Whisky", {0}),
NodeT("Hybesis", {0, 1}),
NodeT("Boudou", {1, 2})});


Yup, that's it!
Great. Since we have all we need, let's define some useful methods.

// Manipulations
int Insert(Node node);                         // Insert a node
void Connect(int idxA, int idxB, bool isBoth); // Add a connection between two nodes

// Node Information
int GetDegree(int idx);              // Return the degree of a node
set< int > GetNeighbors(int idx);    // Return all the outgoing connections from a node


## Manipulations

### Insert / Connect


// Insert a new node and return it's id
int Insert(Node data)
{
nodes.push(data);
return nodes.size() - 1;
}

// Connect two nodes together
void Connect(int idxA, int idxB, bool isBoth)
{
[...] // Checks indexes validity
nodes[idxA].insert(idxB);
if (isBoth) nodes[idxB].insert(idxA);
}

Quite easy, right?!

## Node Information

### GetDegree / GetNeighbors


// Return the degree of a node (number of connections)
int GetDegree(int idx)
{
[...] // Checks index validity
return node[idx].neighbors.size();
}

// Get all outgoing connections of a node
set< int > GetNeighbors(int idx)
{
[...] // Checks index validity
return nodes[idx].neighbors;
}

From this one, we can easily find out the total number of nodes connected to any node, and what these nodes are.
Let's finish the coding by implementing a graph traversal. We will use a simple BFS (Breadth First Search) strategy straight from our Graph definition.

// We use the bool "isVisited" to keep track of our traversal
typedef Node< bool > NodeT;

BFS(int startIdx)
{
auto start = nodes.data()[startIdx];  // Get the start node
start->data = true;                   // Set node to be visited
Queue queue(start);                   // Put node in the queue

// While there is node to be handled in the queue
while (!queue.empty())
{
// Handle the node in the front of the line and get unvisited neighbors
auto node = queue.pop();

// Take neighbors, mark as visited, and add to the queue
auto neighbors = node->GetNeighbors();
for (auto it = neighbors.begin(); it !== neighbors.end(); ++it)
{
auto linkedNode = nodes.data()[*it]; // Retrieve neighbor node

linkedNode->data = true;    // Set visited
}
}
}

Voila ! You can code a GPS now.

## What if I want to add some weights (distances)?

Adjacency Lists can also be used to represent a weighted graph. The weights of edges (links / connections) can be represented as lists of pairs:

[
[{ "idx": 1, "weight": 4 }, { "idx": 2, "weight": 2 }, { "idx": 3, "weight": 0 }],
[{ "idx": 0, "weight": 3 }, { "idx": 2, "weight": 3 }],
[{ "idx": 0, "weight": 4 }, { "idx": 1, "weight": 4 }],
[{ "idx": 0, "weight": 10 }]
] 
Try to implement this yourself as an exercise and try to find find the shortest path in this new graph. You may use a slightly modified version of our BFS algorithm seen above.

Adjacency Lists and Adjacency Matrix are the two most commonly used representations of a graph. Let's compare them shortly with:

- N the number of nodes.
- M the number of edges.
- degree(i) denotes the number of outgoing connections from node i.

Memory space: O(N + M)
Check if two nodes are connected: O(degree(i))
Get all outgoing connections of a node: O(1)
Memory space: O(N * N)
Check if two nodes are connected: O(1)
Get all outgoing connections of a node: O(N)

For the most courageous, we will finish by seeing some trade-off between using STL’s vector, set, or list to represent the nodes (vertices) and the connections (edges). Let's first review some main differences:

Set
A set is automatically sorted
Insert/Delete/Find: O(log n)
Unordered Set
An unordered set is not sorted
Insert/Delete/Find: O(1)
Vector
A vector is not sorted
Insert/Delete/Find: O(n)