Algorithm
An adjacency list is a data structure used to represent relationships or connections between entities in a graph. In a graph, nodes represent entities, and edges represent relationships between those entities. The adjacency list represents these relationships by associating each node with a list of its neighboring nodes.
Here's a brief explanation of how an adjacency list works:
-
Node Representation: Each node in the graph is represented as an object or identifier.
-
List for Each Node: For each node in the graph, there is a corresponding list. This list contains the nodes that are directly connected to the given node.
-
Directed Graphs: In a directed graph, each edge has a direction. If there is an edge from node A to node B, then B is in the adjacency list of A, but A might not be in the adjacency list of B.
-
Undirected Graphs: In an undirected graph, edges have no direction, so the adjacency list for each node includes all nodes that are directly connected to it.
Code Examples
#1 Adjacency List implement in Python
Code -
Python Programming
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, vertex1, vertex2):
# Assuming an undirected graph
if vertex1 in self.adjacency_list:
self.adjacency_list[vertex1].append(vertex2)
if vertex2 in self.adjacency_list:
self.adjacency_list[vertex2].append(vertex1)
def display(self):
for vertex, neighbors in self.adjacency_list.items():
print(f"{vertex}: {neighbors}")
# Example usage:
graph = Graph()
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_vertex("D")
graph.add_edge("A", "B")
graph.add_edge("B", "C")
graph.add_edge("C", "D")
graph.add_edge("D", "A")
graph.display()
#2 Adjacency List implement in Java
Code -
Java Programming
import java.util.*;
public class Graph {
private Map < Integer, List();
}
public void addVertex(int vertex) {
adjacencyList.put(vertex, new LinkedList<>());
}
public void addEdge(int source, int destination) {
// Add edge from source to destination
adjacencyList.get(source).add(destination);
// If the graph is undirected, uncomment the line below
// adjacencyList.get(destination).add(source);
}
public List < Integer> getNeighbors(int vertex) {
return adjacencyList.get(vertex);
}
public void printGraph() {
for (Map.Entry neighbors = entry.getValue();
System.out.print(vertex + " -> ");
for (int neighbor : neighbors) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Graph graph = new Graph();
// Adding vertices
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
// Adding edges
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
// Print the adjacency list
System.out.println("Adjacency List:");
graph.printGraph();
// Get neighbors of a vertex
int vertex = 1;
List < Integer> neighbors = graph.getNeighbors(vertex);
System.out.println("Neighbors of vertex " + vertex + ": " + neighbors);
}
}
#3 Adjacency List implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for the linked list
struct Node {
int data;
struct Node* next;
};
// Graph structure with an array of linked lists
struct Graph {
int vertices;
struct Node** adjacencyList;
};
// Function to create a new node in the linked list
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->vertices = vertices;
// Create an array of linked lists
graph->adjacencyList = (struct Node**)malloc(vertices * sizeof(struct Node*));
// Initialize each linked list as empty
for (int i = 0; i < vertices; ++i) {
graph->adjacencyList[i] = NULL;
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add an edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjacencyList[src];
graph->adjacencyList[src] = newNode;
// Since the graph is undirected, add an edge from dest to src as well
newNode = createNode(src);
newNode->next = graph->adjacencyList[dest];
graph->adjacencyList[dest] = newNode;
}
// Function to print the adjacency list representation of the graph
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->vertices; ++i) {
struct Node* currentNode = graph->adjacencyList[i];
printf("Adjacency list of vertex %d: ", i);
while (currentNode != NULL) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
}
printf("NULL\n");
}
}
// Driver program for testing
int main() {
int vertices = 5;
struct Graph* graph = createGraph(vertices);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
#4 Adjacency List implement in C++
Code -
C++ Programming
#include <iostream>
#include <list>
#include <unordered_map>
class Graph {
private:
std::unordered_map < int, std::list<int>> adjacencyList;
public:
// Add an edge to the graph
void addEdge(int from, int to) {
adjacencyList[from].push_back(to);
adjacencyList[to].push_back(from); // For undirected graph
}
// Print the adjacency list
void printGraph() {
for (const auto& pair : adjacencyList) {
int vertex = pair.first;
const std::list < int>& neighbors = pair.second;
std::cout << "Vertex " << vertex << " is connected to: ";
for (int neighbor : neighbors) {
std::cout << neighbor << " ";
}
std::cout << std::endl;
}
}
};
int main() {
Graph graph;
// Adding edges to the graph
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
// Print the adjacency list
graph.printGraph();
return 0;
}
Demonstration
Adjacency List Data Structure and Algorithm