- Adjacency List
- Matrix of Adjacency
- An Incidence Matrix
This article’s primary topic will be the adjacency list. Let’s first try to understand what a graph truly is before we get into it to understand this idea better.
What is a Graph?
A graph has a fixed number of nodes or vertices. And each node is connected by a line, which we call an edge. The edge is for communication between two vertices or nodes. For example, in the above graph, we see six vertices or nodes ( 0, 1, 2, 3, 4, and 5). From vertex or node 0, we can easily move to vertex 1 and 3 because there is a direct connection between them. But there is no direct connection between vertex or node 0 and 4.
Graphs are used in many real-life applications to solve network problems. For example, on Facebook, the user’s profile is a node or vertex, and the user’s friends in the list are further different nodes or vertices that have direct connections between them.
Types of Graphs
There are primarily two types of graphs, Undirected Graphs and Directed Graphs, both are described in the next sections:
1. Undirected Graph
The undirected graph is very famous because it is a bi-directional graph. For example, below is an example of an undirected graph:
Undirected Graph
In the undirected graph, we can move to any vertex. For example, if there is a connection between nodes A and B, then we can also move from B to A.
2. Directed Graph
In a directed graph, the edges have direction edges. So these arrow edges will tell us how we can move in the graph from one vertex to another vertex, but only in some conditions. For example, if there is a directed edge between the nodes A and B, then we can quickly move from the vertex A to B but not back from B to A if there is no directed edge from B to A.
Directed Graph
Adjacency List
The adjacency list is a list of arrays where the size of the array is equal to the number of nodes present in the graph. And each node also has a sub-array that represents its connectivity to other nodes or vertices. We are going to discuss the adjacency lists of both types of graphs (undirected and directed).
Undirected Graph Adjacency List
In the above undirected graph, we can see six vertices (0, 1, 2, 3, 4, 5). So, we have an array of six vertices. And each further individual vertex has its own linked list or adjacency list, as shown in the previous adjacency list. We can see that vertex 0 points to vertex 4 and vertex 3.
But, as we have explained before, an undirected graph can move in both directions. There is an edge between nodes 0 and 4 and a direct connection between 0 to 4. But due to the undirected graph, there is also a connection between 4 to 0. That’s why if you look into the previous adjacency list, the vertex 4 also points to the vertex 0. The same is also true in the case of vertex 3. The adjacency list of vertex 3 also points to the vertex 0.
Directed Graph Adjacency List
The above image is a directed graph, and on the right side is its adjacency list. In this adjacency list, we can see a direct edge from node 1 to node 2 but not from node 2 to 1. So, we can only move in one direction, that is, from 1 to 2. The same is also in the adjacency list. We can see no link from vertex 2 to 1 in the adjacency list of 2.
Adjacency Matrix
The matrix is used in this method to represent the details of the graph vertices. The size of the matrix depends upon the number of vertices in the graph. For example, if any graph has 5 vertices, then the size of the matrix will be 5 x 5. In this, the row and column are the vertices themselves. The matrix representation of the adjacency list uses either 1 or 0 to fill the matrix. The value of 1 represents a path from row vertex to column vertex, but the value of 0 represents no path between row vertex and column vertex.
Undirected Graph Matrix Adjacency List
In the above matrix adjacency list, we can see that A to E is value 0 because there is no path between them. So, we filled that value with 0. But there is a path from vertex B through A, and we filled that value with 1.
Directed Graph Matrix Adjacency List
In the above-directed matrix adjacency list, we can see that A to D is value 0 because there is no path from A to D, but a path exists from D to A, so we filled that value with 1.
Incidence Matrix
The matrix is used in this method to represent the details of the graph vertices. The size of the matrix depends upon the number of vertices and total edges in the graph. For example, if any graph has 5 vertices and 7 edges, then the size of the matrix will be 5 x 7. The edges will represent the columns, and the vertices will be on the row side. The matrix representation of the adjacency list uses either 0, 1, or -1 to fill the matrix values.
The value of 1 represents an outgoing path from row vertex to column vertex, but the value of 0 represents no path between row vertex and column vertex. The value of -1 represents an incoming path to the edge of the column vertex.
Directed Graph
Adjacency list of directed graph
C++ Code for the Directed Graph Adjacency List
using namespace std;
// Syntax to create node
struct Node
{
int value;
Node* next;
};
// This will store the graph edge details (source and destination)
struct graphEdge {
int source, destination;
};
class GraphAdjacencyList {
// Create a new node for the adjacency list
Node* getNeighbourVertex(int destination, Node* head_node){
Node* new_node = new Node;
new_node->value = destination;
new_node->next = head_node;
return new_node;
}
// It will store the total number of nodes in a graph
int number_of_nodes;
public:
Node **head_node;
GraphAdjacencyList(graphEdge graphEdges[], int num, int number_of_nodes){
// dynamic memory allocation
head_node = new Node*[number_of_nodes]();
this->number_of_nodes = number_of_nodes;
// initialize headnode for every edge of graph
for (int k = 0; k < number_of_nodes; k++) {
head_node[k] = nullptr;
}
for (int k = 0; k < num; k++){
int source = graphEdges[k].source;
int destination = graphEdges[k].destination;
Node* new_node = getNeighbourVertex(destination, head_node[source]);
head_node[source] = new_node;
}
}
~GraphAdjacencyList() {
for (int k = 0; k < number_of_nodes; k++) {
delete[] head_node[k];
}
delete[] head_node;
}
};
void display(Node* displayptr){
while (displayptr != nullptr) {
cout << " adjacency list —> " << displayptr->value;
displayptr = displayptr->next;
}
cout << endl;
}
int main(){
graphEdge graphEdges[] = {
// these are x and y values which represent an edge from x to y
{0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 1}, {3, 4}
};
// total number of nodes from 0 to 5, so total nodes is 6
int number_of_nodes = 6;
// this method will calculate the number of edges in the graph
int num_edges = sizeof(graphEdges)/sizeof(graphEdges[0]);
// create the graph
GraphAdjacencyList graph(graphEdges, num_edges, number_of_nodes);
// display the adjacency list of the graph
for (int k = 0; k < number_of_nodes; k++) {
cout << k;
display(graph.head_node[k]);
}
return 0;
}
Output:
1 adjacency list —> 2
2 adjacency list —> 1 adjacency list —> 0
3 adjacency list —> 4 adjacency list —> 2
4 adjacency list —> 1
5
Directed Graph With Weight Edges
Adjacency list of directed graph
C++ Code for the Directed Graph Adjacency List With Weight
using namespace std;
// Syntax to create node
struct Node {
int value,cost;
Node* next;
};
// This will store the graph edge details (source and destination)
struct graphEdge {
int source, destination,edgeweight;
};
class GraphAdjacencyList {
// Create a new node for the adjacency list
Node* getNeighbourVertex(int destination,int edgeweight,
Node* head_node) {
Node* new_node = new Node;
new_node->value = destination;
new_node->cost = edgeweight;
new_node->next = head_node;
return new_node;
}
// It will store the total number of nodes in a graph
int number_of_nodes;
public:
Node **head_node;
GraphAdjacencyList(graphEdge graphEdges[], int num, int number_of_nodes) {
// dynamic memory allocation
head_node = new Node*[number_of_nodes]();
this->number_of_nodes = number_of_nodes;
// initialize headnode for every edge of graph
for (int k = 0; k < number_of_nodes; k++) {
head_node[k] = nullptr;
}
for (int k = 0; k < num; k++) {
int source = graphEdges[k].source;
int destination = graphEdges[k].destination;
int edgeweight = graphEdges[k].edgeweight;
Node* new_node = getNeighbourVertex(destination, edgeweight,
head_node[source]);
head_node[source] = new_node;
}
}
GraphAdjacencyList() {
for (int k = 0; k < number_of_nodes; k++) {
delete[] head_node[k];
}
delete[] head_node;
}
};
void display(Node* displayptr, int k) {
while (displayptr != nullptr){
cout << "(" << k << ", " <<
displayptr->value << ", " << displayptr->cost << ") ";
displayptr = displayptr->next;
}
cout << endl;
}
int main() {
graphEdge graphEdges[] = {
// (x,y,z)=> these are x and y values which represent an edge
// from x to y with weight w
{0, 1, 4}, {1, 2, 6}, {2, 0, 3}, {2, 1, 5}, {3, 4, 8},
{4, 1, 1}, {3, 2, 7}
};
// total number of nodes from 0 to 5, so total nodes is 6
int number_of_nodes = 6;
// this method will calculate the number of edges in the graph
int num_edges = sizeof(graphEdges)/sizeof(graphEdges[0]);
// create the graph
GraphAdjacencyList graph(graphEdges, num_edges, number_of_nodes);
// display the adjacency list of the graph
for (int k = 0; k < number_of_nodes; k++){
cout << k;
display(graph.head_node[k],k);
}
return 0;
}
Output:
1(1, 2, 6)
2(2, 1, 5) (2, 0, 3)
3(3, 2, 7) (3, 4, 8)
4(4, 1, 1)
5
Conclusion
In this article, we have seen different methods to represent the graph. We have also seen the incidence matrix, which is also a method to represent the graph matrix. Next, we discussed other C++ programming methods to represent the adjacency list (directed and weighted directed graphs). We have also studied directed and undirected graphs. We also came to know that a undirected graph is easy to handle as compared to a directed graph because an undirected graph is a bi-directional graph. After all, it’s not edge direction dependent like the directed graph.
