Data Structures & Algorithms – Graphs (e.g. adjacency list, adjacency matrix)

A graph is a data structure that consists of a finite set of vertices (or nodes) and a set of edges that connect these vertices. There are different ways to represent a graph in computer memory, and two common representations are the adjacency list and the adjacency matrix.

The adjacency list representation of a graph is a collection of linked lists, one for each vertex in the graph. Each list contains the vertices that are adjacent to the corresponding vertex. For example, in an undirected graph, if vertex A is connected to vertex B, then vertex B will also be in the list of vertex A.

Here is an example of how to implement an adjacency list graph in Python using primitives:

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, v1, v2):
        self.adj_list[v1].append(v2)
        self.adj_list[v2].append(v1)

Here is an example of how to implement an adjacency list graph in Java using primitives:

import java.util.LinkedList;

class Graph {
    int numVertices;
    LinkedList<Integer>[] adjList;

    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new LinkedList<Integer>();
        }
    }

    void addEdge(int v1, int v2) {
        adjList[v1].add(v2);
        adjList[v2].add(v1);
    }
}

Here is an example of how to implement an adjacency list graph in Rust using primitives:

struct Graph {
    adj_list: Vec<Vec<usize>>,
}

impl Graph {
    fn new(num_vertices: usize) -> Self {
        Self {
            adj_list: vec![Vec::new(); num_vertices],
        }
    }

    fn add_edge(&mut self, v1: usize, v2: usize) {
        self.adj_list[v1].push(v2);
        self.adj_list[v2].push(v1);
    }
}

On the other hand, the adjacency matrix representation of a graph is a two-dimensional matrix, where each element in the matrix represents an edge between the corresponding vertices. If there is an edge between vertices i and j, the element at position (i, j) in the matrix is set to 1, otherwise it is set to 0.

Here is an example of how to implement an adjacency matrix graph in Python using primitives:

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]

def add_edge(self, v1, v2):
self.adj_matrix[v1][v2] = 1
self.adj_matrix[v2][v1] = 1

Here is an example of how to implement an adjacency matrix graph in Java using primitives:

class Graph {
    int numVertices;
    int[][] adjMatrix;

    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new int[numVertices][numVertices];
    }

    void addEdge(int v1, int v2) {
        adjMatrix[v1][v2] = 1;
        adjMatrix[v2][v1] = 1;
    }
}

Here is an example of how to implement an adjacency matrix graph in Rust using primitives:

struct Graph {
    adj_matrix: Vec<Vec<usize>>,
}

impl Graph {
    fn new(num_vertices: usize) -> Self {
        Self {
            adj_matrix: vec![vec![0; num_vertices]; num_vertices],
        }
    }

    fn add_edge(&mut self, v1: usize, v2: usize) {
        self.adj_matrix[v1][v2] = 1;
        self.adj_matrix[v2][v1] = 1;
    }
}

Both adjacency list and adjacency matrix representations have their own advantages and disadvantages. Adjacency list is more memory efficient for sparse graphs, while adjacency matrix is more memory efficient for dense graphs. In addition, adjacency matrix is more efficient for checking if an edge exists between two vertices, while adjacency list is more efficient for iterating over all edges incident to a vertex.

In conclusion, the choice of representation depends on the characteristics of the graph and the operations that will be performed on it. Both adjacency list and adjacency matrix can be implemented using primitives in Python, JavaScript, Java and Rust.