Adjacency List In C++

In this guide, you will explore the adjacency list in C++ along with various approaches and implementations available.

Graph Representation:

A graph consists of vertices (nodes) and connections (edges) linking these vertices. Graphs come in different classifications such as directed or undirected, weighted or unweighted, cyclic or acyclic, among others. In order to execute algorithms or operations on graphs, they must be structured in a manner that allows computers to effectively handle them.

Adjacency List:

An adjacency list serves as a commonly used method for depicting a graph, particularly when the graph has a sparse nature. Within an adjacency list structure, every vertex within the graph is linked with a list that contains its adjacent vertices. This method effectively conveys the connectivity present within the graph.

An adjacency list serves as a data structure that illustrates relationships between vertices within a graph. It proves especially beneficial for graphs with few connections, where the quantity of edges is notably less than the total potential edges. Within an adjacency list, every vertex within the graph is linked to a roster of its adjacent vertices.

In C++, you have the option to construct an adjacency list utilizing different data structures like an array containing linked lists, a vector comprising vectors, or a map associating vertices with their adjacent nodes.

Directed Graphs:

A directed graph, commonly referred to as a digraph, represents a type of graph where edges are assigned a specific direction to signify a one-way connection between vertices. In contrast to undirected graphs, where edges link vertices without any specified direction, directed graphs portray asymmetric relationships or dependencies among elements.

In a directed graph, every edge is associated with a starting point (tail) and an ending point (head), illustrated by an arrow pointing from the tail to the head. The arrow signifies the orientation of the connection or movement depicted by the edge. This notion of direction imparts distinct features and dynamics to directed graphs compared to undirected graphs.

Method 1: Using an Array of Lists (or vectors)

Let's consider a scenario to grasp the concept of an adjacency list by utilizing an array of linked lists in the C++ programming language.

#include <iostream>
#include <vector>
class DirectedGraph {
private:
 int numVertices;
 std::vector<std::vector<int>> adjacencyList;
public:
 DirectedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList.resize(vertices);
 }
 void addEdge(int src, int dest) {
 // Adding directed edge from src to dest
 adjacencyList[src].push_back(dest);
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " has outgoing edges to: ";
 for (int neighbor : adjacencyList[i]) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 DirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 has outgoing edges to: 1 3 
Vertex 1 has outgoing edges to: 2 
Vertex 2 has outgoing edges to: 3 4 
Vertex 3 has outgoing edges to: 4 
Vertex 4 has outgoing edges to:

Explanation:

• ✅ In this example, the DirectedGraph class uses an array of vectors to create the adjacency list. The addEdge function adds directed edges from the source vertex to the destination vertex. The printGraph function displays the adjacency list for each vertex.
• ✅ The arrows indicate the direction of the edges.
• ✅ The numbers inside the vertices correspond to the vertex numbers .
• ✅ Each vertex points to its outgoing neighbors.
• ✅ It represents a directed graph with directed edges going from the source vertex to the destination vertex.

Directed Graph Visualization:

0 --> 1

3 --> 2 --> 4

Explanation:

• ✅ The code defines a directed graph class that models a directed graph using an adjacency list .
• ✅ The class has a private member variable, numVertices , to store the number of vertices and an adjacency list to store the adjacency list.
• ✅ The constructor initializes the numVertices and resizes the adjacency list vector to match the number of vertices.
• ✅ The addEdge method adds directed edges to the graph by pushing the destination vertex into the vector corresponding to the source vertex in the adjacency list.
• ✅ The printGraph method prints the adjacency list representation. It iterates through each vertex, printing its outgoing neighbors.
• ✅ In the main function , an instance of DirectedGraph named graph with 5 vertices is created.
• ✅ Various edges are added to the graph using the addEdge method , defining the directed relationships.
• ✅ Finally, the printGraph method is called to display the adjacency list representation of the directed graph .
• ✅ The program's result is the output that shows the adjacency list of the directed graph, indicating which vertices each vertex is connected.

Complexity Analysis:

Time Complexity:

The time complexity of the constructor for a DirectedGraph is O(V), where V represents the total number of vertices in the graph.

The addEdge function has a time complexity of O(1) because the process of adding an edge consists of appending to the adjacency list of a vertex.

The time complexity of the printGraph function is O(V + E), where V represents the total number of vertices and E represents the total number of edges. This complexity arises from the iteration process that goes through each vertex and its corresponding neighbors.

Main Function: O(E), where E represents the quantity of edges as edges are incorporated within the main function.

Space Complexity:

Creating a DirectedGraph object involves a time complexity of O(V + E) since it sets up the adjacencyList container and initializes each internal vector for the edges.

The addEdge function operates in constant time per edge, as it simply adds elements to vectors.

The printGraph function has a time complexity of O(V + E) because of the storage requirements for the adjacency list and its vectors.

Main Operation: The complexity of O(V + E) includes the initialization of the graph structure and the insertion of edges.

Where:

V is the number of vertices .

E is the number of edges in the graph.

Method 2: Using Map from Vertices to Neighbors

Let's consider an example to grasp the concept of an adjacency list by utilizing a map that links vertices to their neighboring vertices in C++.

#include <iostream>
#include <map>
#include <vector>
class DirectedGraph {
private:
 int numVertices;
 std::map<int, std::vector<int>> adjacencyList;
public:
 DirectedGraph(int vertices) {
 numVertices = vertices;
 }
 void addEdge(int src, int dest) {
 // Adding directed edge from src to dest
 adjacencyList[src].push_back(dest);
 }
 void printGraph() {
 for (const auto& vertex : adjacencyList) {
 std::cout << "Vertex " << vertex.first << " has outgoing edges to: ";
 for (int neighbor : vertex.second) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 DirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 has outgoing edges to: 1 3 
Vertex 1 has outgoing edges to: 2 
Vertex 2 has outgoing edges to: 3 4 
Vertex 3 has outgoing edges to: 4

Here is a graphical depiction of the directed graph utilizing a mapping from vertices to adjacent nodes:

Directed Graph Visualization:

Vertex 0 --> [1] Vertex 1 --> [2]

Vertex 3 --> [4] Vertex 2 --> [3, 4]

Vertex 4 -->

Explanation:

• ✅ In this example, the code defines a directed graph class that represents a directed graph using a map from vertices to their neighboring vertices. The map is stored as a private member variable named adjacencyList .
• ✅ The constructor initializes the number of vertices.
• ✅ The addEdge function adds a directed edge from the source vertex to the destination vertex by appending the destination to the vector associated with the source vertex key in the adjacency list map.
• ✅ The printGraph function prints the adjacency list representation of the graph by iterating through the map and displaying the outgoing edges for each vertex.
• ✅ In the main function , a DirectedGraph object named graph is created with 5 vertices . Edges are added to the graph using addEdge to create the directed graph structure.
• ✅ After that, the printGraph function is called to display the adjacency list representation of the graph, showing which vertices each vertex point is connected to.

Complexity Analysis:

Time Complexity:

Creating an instance of a DirectedGraph using the constructor has a time complexity of O(V), with V representing the total number of vertices in the graph.

Adding an edge is completed in constant time complexity O(1) since it simply requires appending to the adjacency list of a vertex.

The time complexity of the printGraph function is O(V + E), where V represents the total vertices and E represents the total edges. This is due to the iteration process that involves visiting each vertex and its adjacent neighbors.

Main Procedure: O(E), with E representing the count of edges as new edges are incorporated within the main procedure.

Space Complexity:

Initializing the adjacencyList map to store vertex mappings in the DirectedGraph constructor has a time complexity of O(V), where V represents the number of vertices in the graph.

The addEdge function has a time complexity of O(E), where E represents the total number of edges within the graph. This complexity arises from the necessity to retain all edges within the adjacency list data structure.

The printGraph function has a time complexity of O(V + E) because it involves storing the adjacency list and its vectors.

Primary Operation: O(V + E) consists of initializing the graph instance and incorporating connections.

Where:

V is the number of vertices .

E is the number of edges in the graph.

Undirected Graphs:

An unoriented graph is a key notion in graph theory that illustrates a set of vertices (nodes) and edges (connections) without any specific orientation. Essentially, the associations between vertices are reciprocal - if there is an edge linking vertex A to vertex B, it equally signifies an edge connecting vertex B to vertex A.

Method-1: Using an Array of Lists (or vectors)

Let's consider an illustration to grasp the concept of adjacency list implementation using an array of linked lists in C++.

#include <iostream>
#include <vector>
class UndirectedGraph {
private:
 int numVertices;
 std::vector<std::vector<int>> adjacencyList;
public:
 UndirectedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList.resize(vertices);
 }
 void addEdge(int src, int dest) {
 // Adding undirected edge between src and dest
 adjacencyList[src].push_back(dest);
 adjacencyList[dest].push_back(src);
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (int neighbor : adjacencyList[i]) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 UndirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

Output

0 is connected to: 1 3 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 1 3 4 
Vertex 3 is connected to: 0 2 4 
Vertex 4 is connected to: 2 3

Each number represents a vertex .

The lines between vertices represent edges .

The graph is bidirectional, with edges representing connections that exist in both directions between vertices.

Explanation:

• ✅ In this example, the code defines a class UndirectedGraph that represents an undirected graph using an adjacency list.
• ✅ The class has a private member numVertices to store the number of vertices and an adjacency list to store the adjacency list.
• ✅ The constructor initializes numVertices and resizes the adjacency list vector to match the number of vertices.
• ✅ The addEdge method adds an undirected edge between two vertices by updating their adjacency lists.
• ✅ The printGraph method iterates through vertices and prints their neighbors, displaying the adjacency list.
• ✅ An instance of UndirectedGraph named graph with 5 vertices is created in the main function .
• ✅ Edges are added using the addEdge method to create the connections in the undirected graph .
• ✅ The printGraph method is called to display the adjacency list representation of the graph.

Complexity Analysis:

Time Complexity:

Instantiating an UndirectedGraph constructor has a time complexity of O(V), with V representing the total number of vertices in the graph.

The addEdge function has a time complexity of O(1) since adding an edge consists of appending to the adjacency lists of two vertices.

The time complexity of the printGraph function is O(V + E), where V represents the quantity of vertices and E represents the quantity of edges. This complexity arises from the need to traverse through each vertex and its adjacent neighbors during execution.

Main Operation: O(E), where E represents the quantity of edges due to the addition of edges within the primary function.

Space Complexity:

Creating an instance of an UndirectedGraph with a constructor has a time complexity of O(V) because it adjusts the size of the adjacency list vector to correspond with the number of vertices.

The addEdge function has a time complexity of O(1) per edge because it simply adds elements to vectors.

The printGraph Function has a time complexity of O(V + E) because it involves storing the adjacency list.

The primary task in O(V + E) is to generate the graph instance and incorporate connections between vertices.

Where:

V is the number of vertices .

E is the number of edges in the graph.

Method 2: Using an Array of Deques

We utilize an array of deques (double-ended queues) to depict an undirected graph. Each deque holds integers that correspond to neighboring vertices linked by an edge to the current vertex. This method is appropriate for undirected graphs, where edges are bidirectional and connect vertices in both directions.

#include <iostream>
#include <deque>
class UndirectedGraph {
private:
 int numVertices;
 std::deque<int>* adjacencyList;
public:
 UndirectedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList = new std::deque<int>[vertices];
 }
 void addEdge(int src, int dest) {
 adjacencyList[src].push_back(dest);
 adjacencyList[dest].push_back(src); // For undirected graphs
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (int neighbor : adjacencyList[i]) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
 ~UndirectedGraph() {
 delete[] adjacencyList;
 }
};
int main() {
 UndirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 is connected to: 1 3 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 1 3 4 
Vertex 3 is connected to: 0 2 4 
Vertex 4 is connected to: 2 3

Explanation:

• ✅ In this example, the code defines a class named UndirectedGraph to represent an undirected graph .
• ✅ The class includes a private member variable, numVertices , to store the number of vertices in the graph.
• ✅ The adjacency list is implemented as an array of deques (double-ended queues) , where each deque represents a vertex in the graph.
• ✅ The class constructor takes the number of vertices as a parameter and initializes the numVertices variable .
• ✅ It dynamically allocates memory for an array of deques, each corresponding to a vertex in the graph.
• ✅ The addEdge method allows an undirected edge between two vertices ( src and dest ).
• ✅ It pushes integers into the deque associated with the source and destination vertices. This operation ensures the graph is undirected , adding the edge in both directions.
• ✅ The printGraph method is used to display the adjacency list representation of the graph.
• ✅ It iterates through each vertex in the graph (from 0 to numVertices - 1 ) and prints the neighbors stored in the associated deque.
• ✅ The class includes a destructor to release the dynamically allocated memory for the array of deques when the object is destroyed.
• ✅ In the main function , an instance of the UndirectedGraph class is created with 5 vertices .
• ✅ Several edges are added to the graph using the addEdge method to establish connections between vertices .
• ✅ Finally, the printGraph method displays the adjacency list representation of the undirected graph.

Complexity Analysis:

Time Complexity:

• ✅ The time complexity for creating an array of deques is O(V) , where V is the number of vertices.
• ✅ After that, pushing an integer into a deque takes constant time, O(1) .
• ✅ Adding an edge between two vertices ( src and dest ) results in two constant-time operations (one for each direction) for undirected graphs .
• ✅ If there are E edges , the total time complexity for adding edges is O(E) .
• ✅ The method iterates through each vertex (V) and its neighbors (E), resulting in a time complexity of O(V + E) .
• ✅ Deleting the array of deques takes O(V) time complexity.
• ✅ Overall, the time complexity is dominated by adding edges and printing the graph, making it O(V + E) .

Space Complexity:

• ✅ The space complexity of the array of deques is O(V) , where V is the number of vertices.
• ✅ Two integers (representing neighbors) are stored for each edge , one in each direction for undirected graphs .
• ✅ If there are E edges , the space complexity for storing integers is O(2E) , which simplifies to O(E) .
• ✅ The total space complexity is the sum of the space used by the array of deques and the integers within them, which is O(V + E) .

Method-3: Using Map from Vertices to Neighbors

Here is a way to illustrate an undirected graph in C++ by utilizing a map that maps vertices to their adjacent nodes:

#include <iostream>
#include <map>
#include <set>
class UndirectedGraph {
private:
 std::map<int, std::set<int>> adjacencyList;

public:
 void addEdge(int src, int dest) {
 // Adding undirected edge between src and dest
 adjacencyList[src].insert(dest);
 adjacencyList[dest].insert(src);
 }
 void printGraph() {
 for (const auto& vertex : adjacencyList) {
 std::cout << "Vertex " << vertex.first << " is connected to: ";
 for (int neighbor : vertex.second) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 UndirectedGraph graph;
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 is connected to: 1 3 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 1 3 4 
Vertex 3 is connected to: 0 2 4 
Vertex 4 is connected to: 2 3

Explanation:

• ✅ In this example, the code defines a class named UndirectedGraph that represents an undirected graph using a map from vertices to their neighbors. It also uses the C++ standard library's std::set to store neighbors in sorted order.
• ✅ The addEdge method in the UndirectedGraph class adds undirected edges to the graph. It takes two vertex indices, src and dest , and adds both vertices to each other's adjacency lists using std::set to ensure that neighbors are stored in sorted order. This way, the same edge is not added multiple times.
• ✅ The printGraph method is used to print the adjacency list of the graph. It iterates through each vertex in the adjacency list (adjacency list) and prints the neighbors associated with each vertex.
• ✅ An instance of the UndirectedGraph class named graph is created.
• ✅ Several undirected edges are added to the graph using the addEdge method .
• ✅ The printGraph method is called to display the adjacency list representation of the graph.
• ✅ The code focuses on maintaining a clean adjacency list representation for an undirected graph using a map and sorted sets of neighbors.

Complexity Analysis:

Time Complexity:

• ✅ Inserting elements into a std::set takes O(log N) , where N is the number of neighbors for a vertex . Since each edge involves adding two vertices to their respective sets , the total time complexity for adding all edges would be O(E * log V) , where E is the number of edges and V is the number of vertices.
• ✅ This function iterates through each vertex in the adjacency list and its associated neighbors, which takes O(V + E) time , where V is the number of vertices and E is the number of edges .
• ✅ Adding edges takes O(E * log V) time.

Space Complexity:

The storage of the adjacency list and sets determine the space complexity :

• ✅ The space required for the adjacency list is O(V + E) , where V is the number of vertices and E is the number of edges.
• ✅ Each set of neighbors uses O(N) space , where N is the average number of neighbors for each vertex.
• ✅ Overall space complexity is O(V + E + V * N) , which simplifies to O(V + E) if the average number of neighbors is not significantly larger than the number of vertices.

Weighted Graph:

A weighted graph is a specific kind of graph where every edge is assigned a numerical value referred to as a "weight." This weight serves as a quantitative indicator of various attributes such as cost, distance, significance, or any other metric linked to the relationship between the connected vertices. Essentially, the weight of an edge offers supplementary details regarding the connection between the vertices it joins.

In a weighted graph:

• ✅ Each edge has an associated weight representing various quantities such as distance, cost, time, capacity , or any other relevant measure.
• ✅ The weights can be positive, negative , or zero , depending on the context and the meaning of the weight.
• ✅ Weighted graphs are used to model scenarios where the relationships between nodes have varying levels of significance, cost , or impact .

For instance, imagine a situation where nodes symbolize urban areas and connections symbolize highways linking them. Here, the values assigned to the connections might signify the distances between cities. Likewise, values can indicate the monetary transfers between accounts within a financial system. Weighted graphs offer flexibility and are utilized in a range of fields like transportation, social connections, network navigation, and resource distribution.

Method-1: Using an Array of Lists (or vectors)

Here is a demonstration of how you can depict a weighted graph by utilizing an array of vectors to hold the adjacency list in C++:

#include <iostream>
#include <vector>
class WeightedGraph {
private:
 int numVertices;
 std::vector<std::vector<std::pair<int, int>>> adjacencyList;
public:
 WeightedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList.resize(vertices);
 }
 void addEdge(int src, int dest, int weight) {
 // Adding weighted edge from src to dest with a given weight
 adjacencyList[src].emplace_back(dest, weight);
 // Uncomment the line below for an undirected graph
 // adjacencyList[dest].emplace_back(src, weight);
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (const auto& neighbor : adjacencyList[i]) {
 std::cout << neighbor.first << " (Weight: " << neighbor.second << ") ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 WeightedGraph graph(5);
 graph.addEdge(0, 1, 2);
 graph.addEdge(0, 3, 5);
 graph.addEdge(1, 2, 3);
 graph.addEdge(2, 3, 1);
 graph.addEdge(2, 4, 4);
 graph.addEdge(3, 4, 6);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 is connected to: 1 (Weight: 2) 3 (Weight: 5) 
Vertex 1 is connected to: 2 (Weight: 3) 
Vertex 2 is connected to: 3 (Weight: 1) 4 (Weight: 4) 
Vertex 3 is connected to: 4 (Weight: 6) 
Vertex 4 is connected to:

Explanation:

• ✅ In this example, the code defines a class named WeightedGraph that represents a weighted graph using an array of vectors to store the adjacency list . Each element of the adjacency list is a vector containing pairs representing the destination vertex and the weight of the edge .
• ✅ The constructor initializes the number of vertices and resizes the adjacency list vector accordingly.
• ✅ The addEdge method allows adding weighted edges to the graph. It takes the source vertex, destination vertex , and weight as input. The method appends a pair containing the destination vertex and weight to the vector at the source vertex's position in the adjacency list . Additionally, we can uncomment the corresponding line to add the reverse edge for an undirected graph .
• ✅ The printGraph method is used to display the adjacency list representation of the graph. It iterates through each vertex and its associated neighbors (pairs) in the adjacency list and prints the destination vertex along with the weight of the edge.
• ✅ An instance of the WeightedGraph class named graph is created in the main function . Several weighted edges are added to the graph using the a ddEdge method. After that, the printGraph method is called to display the adjacency list representation of the graph, showing the connections between vertices and the associated edge weights.
• ✅ This code demonstrates how to represent a weighted graph using an array of vectors and incorporate edge weights into the graph structure.

Complexity Analysis:

Time Complexity:

• ✅ Adding an edge involves appending to the adjacency list of the source vertex, which takes O(1) time .
• ✅ This function iterates through each vertex in the adjacency list and its associated neighbors (pairs), resulting in a time complexity of O(V + E) , where V is the number of vertices and E is the number of edges .
• ✅ Adding edges using the addEdge method takes O(E) time .

Space Complexity:

The space complexity is determined by the storage of the adjacency list and the pairs representing edges:

• ✅ The space required for the adjacency list is O(V + E), where V is the number of vertices and E is the number of edges.
• ✅ Each pair representing an edge uses O(1) space .
• ✅ Overall space complexity is O(V + E) due to the adjacency list and the pairs.

Where:

V is the number of vertices .

E is the number of edges in the graph.

Method 2: Using Map from Vertices to Neighbors

Here is an illustration demonstrating how a weighted graph can be depicted using a mapping from nodes to their adjacent nodes, with each adjacent node having a corresponding weight:

#include <iostream>
#include <map>
class WeightedGraph {
private:
 std::map<int, std::map<int, int>> adjacencyList;
public:
 void addEdge(int src, int dest, int weight) {
 // Adding weighted edge from src to dest with a given weight
 adjacencyList[src][dest] = weight;
 // Uncomment the line below for an undirected graph
 // adjacencyList[dest][src] = weight;
 }
 void printGraph() {
 for (const auto& vertex : adjacencyList) {
 std::cout << "Vertex " << vertex.first << " is connected to: ";
 for (const auto& neighbor : vertex.second) {
 std::cout << neighbor.first << " (Weight: " << neighbor.second << ") ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 WeightedGraph graph;
 graph.addEdge(0, 1, 2);
 graph.addEdge(0, 3, 5);
 graph.addEdge(1, 2, 3);
 graph.addEdge(2, 3, 1);
 graph.addEdge(2, 4, 4);
 graph.addEdge(3, 4, 6);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 is connected to: 1 (Weight: 2) 3 (Weight: 5) 
Vertex 1 is connected to: 2 (Weight: 3) 
Vertex 2 is connected to: 3 (Weight: 1) 4 (Weight: 4) 
Vertex 3 is connected to: 4 (Weight: 6)

Explanation:

• ✅ In this example, the code defines a class named WeightedGraph that represents a weighted graph using a map from vertices to neighbors, where each neighbor is associated with a weight.
• ✅ The addEdge method allows adding weighted edges to the graph. It takes the source vertex, destination vertex , and weight as input. The method updates the inner map associated with the source vertex to include the destination vertex as a neighbor, along with the weight of the edge. You can uncomment the corresponding line to add the reverse edge for an undirected graph .
• ✅ The printGraph method is used to display the adjacency list representation of the graph. It iterates through each vertex in the outer map and its associated neighbors (inner map) to print the destination vertex and the weight of the edge.

At the main function:

• ✅ An instance of the WeightedGraph class named graph is created.
• ✅ Several weighted edges are added to the graph using the addEdge method .
• ✅ After that, the printGraph method is called to display the adjacency list representation of the graph, showing the connections between vertices and the associated edge weights.

Complexity Analysis:

Time Complexity:

• ✅ Adding an edge involves updating the inner map associated with the source vertex, which takes O(log N) time , where N is the average number of neighbors for a vertex.
• ✅ This function iterates through each vertex in the adjacency list and its associated neighbors ( inner map ), resulting in a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.
• ✅ Adding edges using the addEdge method takes O(E * log N) time .

Space Complexity:

The space complexity is determined by the storage of the adjacency list and the maps representing edges:

• ✅ The space required for the adjacency list is O(V + E) , where V is the number of vertices and E is the number of edges.
• ✅ Each inner map associated with a vertex uses O(N) space , where N is the average number of neighbors for a vertex.
• ✅ Overall space complexity is O(V + E + V N), which simplifies to O(V + E + E log N) or simply O(V + E) if N is not significantly larger than the number of vertices.

Method-3: Using an Array of Deques

We utilize an array of deques (double-ended queues) to store a weighted graph, where each deque holds pairs of integers. These integer pairs denote the neighboring vertex and the edge weight that links the current vertex to its neighbor.

#include <iostream>
#include <deque>
class WeightedGraph {
private:
 int numVertices;
 std::deque<std::pair<int, int>>* adjacencyList;
public:
 WeightedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList = new std::deque<std::pair<int, int>>[vertices];
 }
 void addEdge(int src, int dest, int weight) {
 adjacencyList[src].push_back(std::make_pair(dest, weight));
 adjacencyList[dest].push_back(std::make_pair(src, weight)); // For undirected graphs
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (const auto& neighbor : adjacencyList[i]) {
 std::cout << neighbor.first << " (Weight: " << neighbor.second << ") ";
 }
 std::cout << "\n";
 }
 }
 ~WeightedGraph() {
 delete[] adjacencyList;
 }
};
int main() {
 WeightedGraph graph(5);
 graph.addEdge(0, 1, 2);
 graph.addEdge(0, 3, 5);
 graph.addEdge(1, 2, 3);
 graph.addEdge(2, 3, 1);
 graph.addEdge(2, 4, 4);
 graph.addEdge(3, 4, 6);
 graph.printGraph();
 return 0;
}

Output

Vertex 0 is connected to: 1 (Weight: 2) 3 (Weight: 5) 
Vertex 1 is connected to: 0 (Weight: 2) 2 (Weight: 3) 
Vertex 2 is connected to: 1 (Weight: 3) 3 (Weight: 1) 4 (Weight: 4) 
Vertex 3 is connected to: 0 (Weight: 5) 2 (Weight: 1) 4 (Weight: 6) 
Vertex 4 is connected to: 2 (Weight: 4) 3 (Weight: 6)

Explanation:

• ✅ In this example, the code defines a class named weighted graph to represent a weighted graph.
• ✅ It includes a private member variable, numVertices , to store the number of vertices in the graph.
• ✅ The class constructor takes the number of vertices as a parameter and initializes the numVertices variable .
• ✅ It dynamically allocates memory for an array of deques , each corresponding to a vertex in the graph.
• ✅ The adjacency list is implemented as an array of deques containing pairs of integers. Each pair consists of the neighbor vertex and the weight of the edge connecting the current vertex to that neighbor.
• ✅ The addEdge method allows adding a weighted edge between two vertices ( src and dest ) with a specified weight.
• ✅ It pushes a pair into the deque associated with the source and destination vertices. This pair includes the neighbor vertex (dest) and the edge weight connecting the current vertex (src) to that neighbor.
• ✅ For undirected graphs, it also adds the reverse edge to ensure symmetric relationships between vertices.
• ✅ The printGraph method is used to display the adjacency list representation of the graph.
• ✅ It iterates through each vertex in the graph (from 0 to numVertices - 1 ) and prints the neighbors and their associated edge weights.
• ✅ The class includes a destructor to release the dynamically allocated memory for the array of deques when the object is destroyed.
• ✅ In the main function, an instance of the WeightedGraph class is created, and several weighted edges are added to the graph using the addEdge method . Finally, the printGraph method is called to display the adjacency list representation of the graph, including the vertices, their neighbors, and edge weights.
• ✅ This code provides a clear and efficient representation of a weighted graph using an array of deques. It is suitable for various applications where weighted edges and efficient neighbor traversal are essential.

Complexity Analysis:

Time Complexity:

• ✅ The time complexity for creating an array of deques is O(V) , where V is the number of vertices.
• ✅ Pushing a pair into a deque takes constant time, O(1) .
• ✅ Adding an edge between two vertices results in two constant-time operations for undirected graphs .
• ✅ If there are E edges , the total time complexity for adding edges is O(E) .
• ✅ The method iterates through each vertex and its neighbors, resulting in a time complexity of O(V + E), where V is the number of vertices, and E is the number of edges.
• ✅ Deleting the array of deques takes O(V).
• ✅ Therefore, the time complexity is dominated by adding edges and printing the graph, making it O(V + E) .

Space Complexity:

• ✅ The space complexity of the array of deques is O(V) , where V is the number of vertices.
• ✅ A pair ( neighbor vertex, edge weight ) is stored twice for undirected graphs for each edge.
• ✅ If there are E edges , the space complexity for storing pairs is O(2E) , which simplifies to O(E).
• ✅ The total space complexity is the sum of the space used by the array of deques and the pairs in the deques, which is O(V + E) .

Applications of Adjacency lists:

Adjacency lists are frequently employed to represent graphs because of their effectiveness in a wide range of scenarios. Below are some typical uses of adjacency lists:

Social Media Platforms: On platforms such as Facebook, Twitter, and LinkedIn, each individual user can be symbolized as a vertex within a graph. The relationships they establish, like friendships and followers, can then be depicted through adjacency lists.

Recommendation Systems: Numerous recommendation techniques propose items, goods, or acquaintances based on graph architectures. Utilizing the adjacency list format aids in depicting associations and links among users or products, enhancing the precision of recommendations.

In the realm of computer networks, adjacency lists serve as a depiction of a network's structure. These lists play a crucial role in determining the most efficient routes, enhancing data transmission pathways, and ensuring optimal utilization of network assets.

In the realm of game development, adjacency lists are often employed to simulate game environments. Within this context, vertices symbolize various locations or scenes, while edges signify potential movements between scenes.

When working with clustering algorithms, similarity relationships among data points can be depicted using adjacency lists. In this context, each vertex corresponds to a specific data point, while edges serve to indicate similarity metrics.

Graph Algorithms: Several graph algorithms, like depth-first search (DFS), breadth-first search (BFS), Dijkstra's algorithm, and Prim's algorithm, perform effectively when using the adjacency list format. This format enables rapid retrieval of neighboring nodes and their relevant data.

Benefits:

Memory Optimization: Adjacency lists prove to be efficient in terms of memory usage for sparse graphs since they solely retain data pertaining to present edges. This characteristic renders them appropriate for graphs that have a lower edge count compared to the maximum potential edges.

Navigating through a vertex's adjacent vertices is uncomplicated when using adjacency lists. Moving through the adjacency list of a vertex requires time proportional to the number of neighbors, thereby enhancing the efficiency of certain graph algorithms.

Adjacency lists are particularly suitable for scenarios where the graph undergoes changes over time. The addition or deletion of edges and vertices can be carried out with efficiency, ensuring minimal impact on the overall data structure.

In scenarios where the level of connectivity differs significantly among vertices, adjacency lists prove to be more memory-efficient compared to adjacency matrices.

Limitations:

For graphs that are densely connected, adjacency lists may require more memory compared to adjacency matrices, resulting in lower memory efficiency.

Neighbor Search Time: Although adjacency lists excel in navigating neighboring vertices, determining the direct connection between two vertices (edge existence) requires O(degree) time, with degree representing the average neighbor count.

In weighted graphs, adjacency lists necessitate additional storage space for preserving the edge weights. Accessing the edge weights could potentially result in increased time consumption as it involves searching for the particular neighboring element.

Deleting an edge from an adjacency list involves searching for the specific edge and potentially adjusting the size of the list. This process may not be as efficient as deleting an edge in an adjacency matrix.

Graph Representation Trade-off: Deciding between adjacency lists and matrices relies on the unique attributes of the graph and the nature of the operations executed. Certain algorithms could benefit from matrices for their ability to quickly determine edge existence in constant time.