Adjacency List 🎯

Welcome to our comprehensive guide on Adjacency List! This lesson is designed to help you understand this essential data structure, suitable for both beginners and intermediate learners. Let's dive into the world of Adjacency List, a practical and real-world-oriented concept that will enhance your programming skills.

Understanding Adjacency List 📝

An Adjacency List is a data structure used to represent a finite graph. It's particularly useful in various real-life scenarios, such as mapping relationships between entities in social networks, representing road networks, or even simulating the spread of diseases in a population.

Basic Concepts 💡

Vertex (or Node): A vertex, also known as a node, is an entity in the graph. In a social network, each person could be a vertex. In a road network, each intersection or city could be a vertex.
Edge: An edge is a connection between two vertices. In a social network, a friendship or a relationship could be an edge. In a road network, a road between two cities could be an edge.
Adjacency List: An adjacency list is a collection of lists where each list describes the vertices (or nodes) that are adjacent to a given vertex.

Let's illustrate this with a simple example:

Vertex A ------> Vertex B
|             |
|             |
Vertex C ------> Vertex D

In this example, we have four vertices (A, B, C, and D). An adjacency list for this graph could look like this:

Vertex A: [Vertex B]
Vertex B: []
Vertex C: [Vertex D]
Vertex D: []

Now that we've understood the basic concept, let's discuss how to represent an adjacency list in code.

Implementing Adjacency List 📝

For our implementation, we will use Python.

python

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def addEdge(self, u, v):
        self.graph.append([u, v])

# Creating a graph
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 2)

In the above code, we have created a simple graph with 4 vertices and 5 edges. The addEdge function adds an edge between two vertices in the graph.

📝 Note: In the adjacency list representation, the graph is stored as an array of lists. Each sub-list contains the vertices that are adjacent to the indexed vertex.

Traversing the Adjacency List 💡

To traverse the adjacency list, we'll use Depth-First Search (DFS) algorithm.

python

def dfs(vertex, visited, recursive):
    visited[vertex] = True
    print(vertex, end=" ")
    recursive[vertex] = True

    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            dfs(neighbor, visited, recursive)

# Traversing the graph
visited = [False] * V
recursive = [False] * V
dfs(0, visited, recursive)

In the above code, we define a DFS function to traverse the graph starting from a vertex. The visited list keeps track of the visited vertices, while the recursive list prevents cyclic traversal.

Quiz Time 💡

By understanding and implementing the Adjacency List, you've taken the first step towards mastering essential graph algorithms. As you continue your programming journey, you'll find many practical applications for this versatile data structure. Happy coding! 🎉