Tutorial Playlist
An adjacency list is an essential data structure used to construct graphs. Graphs are composed of vertices and edges, the latter showing connections between nodes. In an adjacency list, each vertex in the graph is linked to a list of its neighboring vertices. This structure has gained a lot of popularity among data scientists because it is convenient for storing sparse graphs (graphs with a small number of connections between vertices) and allows traversing the graph.
Adjacency lists are the data structures used to represent graphs. In the representation, each vertex (or node) of the graph is accompanied by a list of its neighboring vertices. Let V be a vertex; then, the list for V contains all the vertices connected with V, that is, the vertices incident on V by the edge. The list notation is particularly useful for sparse graphs when the number of edges is much lower than the number of possible edges.
An adjacency list consists of two main components:
Example Representation:
Let's consider a simple undirected graph with vertices A, B, C, and D with the subsequent edges:
The adjacency list representation for this graph would be:
A: [B, D]
B: [A, C]
C: [B]
D: [A]
In this representation,
Every line symbolizes a vertex that has neighboring vertices.
Graphs are mathematical structures that are used to represent relationships between objects relating to each other in pairs. They consist of two main components: vertices (also called nodes) and edges. Nodes stand for things, and lines are used to demonstrate ties between them. Charts are predominantly utilized in such areas as computer science, mathematics, biology, and social sciences, mostly thanks to their ability to model very intricate relationships.
Graphs can be either directed or undirected based on whether the edges have a specific direction or not. In directed graphs, the directed edges have the direction, while in undirected graphs the edges do not have the direction. Besides the weighted graphs where each edge has a numerical value or weight that is used as the strength or cost of the connection between the vertices.
There are many ways to represent graphs, each with its own advantages and use cases:
The representations have different space as well as time complexities depending on the operations like edge insertion, deletion, and traversal. These factors also determine the suitability of these structures in different scenarios under the specific requirements of the application.
For implementing adjacency lists, you can use a data structure that is good at storing and retrieving the neighbors of each vertex efficiently. One of the mentioned algorithms is to apply a hash table (or dictionary in some languages) in which the keys are the vertices and the values are lists that hold the neighbors of each vertex.
Here is a basic outline of the adjacency list in the data structure in Python:
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, vertex):
if vertex not in self.adj_list:
self.adj_list[vertex] = []
def add_edge(self, src, dest):
if src in self.adj_list and dest in self.adj_list:
self.adj_list[src].append(dest)
# If the graph is undirected, uncomment the line below
# self.adj_list[dest].append(src)
def get_neighbors(self, vertex):
return self.adj_list.get(vertex, [])
def __str__(self):
return str(self.adj_list)
The implementation provides you with an array of services, like adding vertices and edges to the graph and searching for neighbors of a particular vertex.
The adjacency list in Python is fundamental to graph theory and has numerous applications across various domains.
The lists are the base data structure in graph theory and they have many applications in graph algorithms, network analysis, social network analysis, and recommendation systems. They allow the use of entities and their relationships and consequently are an essential component of many fields of study.
1. Graph Algorithms:
2. Network Analysis:
3. Social Network Analysis:
4. Recommendation Systems:
In these cases, adjacency is the fundamental data structure that enables the effective representation and analysis of the relationships between entities in different real-world situations. They are vital for executing tasks such as algorithms running, recommendations being made, and networks and relationships being understood.
Adjacency lists are an amazing and useful data structure that can be used in lots of different ways all over the world. By presenting social networks and transportation systems together, the lists are used to represent the relationships between entities and to optimize various algorithms.
The lists are so efficient in storing and traversing graphs that they are already being used for real-world applications, such as Facebook's social graph, Google Maps' routing algorithm, and Netflix's recommendation system. Through the use of these lists, the platforms provide personalized experiences, optimize resource utilization, and, at the same time, improve the satisfaction of users.
1. What are the features of the adjacency list?
Adjacency list represents a graph as an array of lists. Each array element represents a vertex of the graph.
2. Why is an adjacency list needed?
Adjacency lists are needed to efficiently represent and work with graphs, especially sparse ones, where there are relatively few edges compared to the total number of possible edges.
3. What is adjacent in data structure?
In the data structure, "adjacent" refers to vertices that are directly connected by an edge.
4. What are adjacencies in a graph?
Adjacencies in a graph refer to the relationships between vertices, indicating which vertices are directly connected by edges.
5. What data type is an adjacency list?
An adjacency list is typically implemented using arrays (or lists) of lists. The outer list represents vertices, and each inner list contains the adjacent vertices.
6. How do you use an adjacency list?
To use an adjacency list, you typically create a list where each element corresponds to a vertex in the graph. Each element holds a list of adjacent vertices. This structure allows efficient access to adjacent vertices and easy traversal of the graph.
7. What is the size of the adjacency list?
The size of an adjacency list is equal to the number of vertices in the graph.
8. What is the space used for the adjacency list?
The space used by an adjacency list depends on the number of vertices and edges in the graph. In general, for a graph with V vertices and E edges, the space complexity of the adjacency list is O(V + E). For sparse graphs, it is often more memory-efficient compared to other representations like adjacency matrices.
Mukesh kumar
Talk to our experts. We’re available 24/7.
Indian Nationals
1800 210 2020
Foreign Nationals
+918045604032
upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enrolling. upGrad does not make any representations regarding the recognition or equivalence of the credits or credentials awarded, unless otherwise expressly stated. Success depends on individual qualifications, experience, and efforts in seeking employment.
upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...