# C++ : Adjacency list implementation for storing graph

Below is a simple example of a graph where each node has a number that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list can be implemented as a list of lists in C++.

Example : In the below adjacency list we can see
a) Node 0 has a list storing adjacent nodes 1 and 2.
b) Node 1 has a list storing adjacent nodes 0, 3 and 4. C++: Storing graph in an adjacency list using list of lists.

``````#include<iostream>
#include<list>

using namespace std;

class Graph {

private:

int nodes;

public:

Graph() {
}

Graph (int nodes) { // Allocate resources
this->nodes = nodes;
}

~Graph () { // Free allocated resources
}

void AddEdge (int src, int dst) {
}

void Iterate (int src) {
cout <<  src << " : ";
cout << adj_node << " ";
} cout << endl;
}
};

int main()
{
Graph g(7);

cout << "Adjacency list implementation for graph" << endl;

g.Iterate(0);
g.Iterate(1);
g.Iterate(4);

return 0;
}
``````

Output

``````Adjacency list implementation for graph
0 : 1 2
1 : 0 3 4
4 : 1 6
``````

#### Storing graph as an adjacency list using a map of node and list of nodes

Below is an example of a graph where each node has a name (string) and an id (number) that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list for such a graph can be implemented as a map of node and list of nodes in C++.

Example : In the below adjacency list we can see
a) Node ( Alfa, 1 ) has a list storing adjacent nodes ( Cod, 2 ), ( Pi, 3 ) and ( Ram , 4)

Note : Node is defined as a custom class hence we need to overload < (less than) operator so that it works with map other option is to use a compare class that overloads () operator. C++: Storing graph in an adjacency list using map of Node and a list of Node(s).
Operator < (less than) is overloaded.

``````#include<list>
#include<map>

using namespace std;

class Node {

private:

string name;
int id;

public:

Node(string arg_name, int arg_id): name(arg_name), id(arg_id) {
}

bool operator < (const Node& n) const {
if (n.name < this->name) {
return true;
}
return false;
}

void Display () const {
cout << "(" << name << " , " << id << ") ";
}
};

class Graph {

private:

public:

Graph() {
}

}

void Iterate (Node src) {

src.Display(); cout << " : ";

for (const auto& node : adjlist[src]) {
node.Display();
} cout << endl;
}
};

int main()
{
Node n1("Alfa", 1);
Node n2("Cod", 2);
Node n3("Pi", 3);
Node n4("Ram", 4);
Node n5("Yo", 5);

list<Node> n1_list = { n2, n3, n4 };
list<Node> n2_list = { n1, n4 };
list<Node> n3_list = { n1, n4, n5 };
list<Node> n4_list = { n1, n2, n3, n5 };
list<Node> n5_list = { n3, n4 };

cout << "Adjacency list implementation for graph" << endl;

Graph g;

g.Iterate(n1);
g.Iterate(n2);
g.Iterate(n3);
g.Iterate(n4);

return 0;
}
``````

Output

``````Adjacency list implementation for graph
(Alfa , 1)  : (Cod , 2) (Pi , 3) (Ram , 4)
(Cod , 2)  : (Alfa , 1) (Ram , 4)
(Pi , 3)  : (Alfa , 1) (Ram , 4) (Yo , 5)
(Ram , 4)  : (Alfa , 1) (Cod , 2) (Pi , 3) (Yo , 5)
``````

C++: Storing graph in an adjacency list using map of Node and a list of Node(s).
Creating a map using a Compare Class with operator () overloaded.

``````#include<iostream>
#include<list>
#include<map>

using namespace std;

class Node {

private:

string name;
int id;

public:

Node(string arg_name, int arg_id): name(arg_name), id(arg_id) {
}

void Display () const {
cout << "(" << name << " , " << id << ") ";
}

int GetId() const {
return id;
}
};

class Compare {

public:
bool operator () (const Node& a, const Node& b) const {
return (a.GetId() < b.GetId());
}
};

class Graph {

private:

public:

Graph() {
}

}

void Iterate (Node src) {

src.Display(); cout << " : ";

for (auto& node : adjlist[src]) {
node.Display();
} cout << endl;
}
};

int main()
{
Node n1("Alfa", 1);
Node n2("Cod", 2);
Node n3("Pi", 3);
Node n4("Ram", 4);
Node n5("Yo", 5);

list<Node> n1_list = { n2, n3, n4 };
list<Node> n2_list = { n1, n4 };
list<Node> n3_list = { n1, n4, n5 };
list<Node> n4_list = { n1, n2, n3, n5 };
list<Node> n5_list = { n3, n4 };

cout << "Adjacency list implementation for graph" << endl;

Graph g;

g.Iterate(n1);
g.Iterate(n2);
g.Iterate(n3);
g.Iterate(n4);

return 0;
}
``````

Output

``````Adjacency list implementation for graph
(Alfa , 1)  : (Cod , 2) (Pi , 3) (Ram , 4)
(Cod , 2)  : (Alfa , 1) (Ram , 4)
(Pi , 3)  : (Alfa , 1) (Ram , 4) (Yo , 5)
(Ram , 4)  : (Alfa , 1) (Cod , 2) (Pi , 3) (Yo , 5)
``````