Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 9.2 Basic Operations on Graphs

Basic operations on graphs can be divided into operations on "edges" and operations on "vertices". Their implementations differ depending on whether the graph is represented as an "adjacency matrix" or an "adjacency list".

## 9.2.1 Implementation Based on Adjacency Matrix

Given an undirected graph with \(n\) vertices, the various operations are implemented as shown in Figure 9-7.

- Adding or removing an edge: Directly modify the specified edge in the adjacency matrix, using \(O(1)\) time. Since it is an undirected graph, both directions of the edge need to be updated simultaneously.
- Adding a vertex: Add a row and a column at the end of the adjacency matrix and fill them all with \(0\)s, using \(O(n)\) time.
- Removing a vertex: Delete a row and a column in the adjacency matrix. The worst case occurs when removing the first row and column, requiring \((n-1)^2\) elements to be "moved up and to the left", thus using \(O(n^2)\) time.
- Initialization: Given \(n\) vertices, initialize a vertex list `vertices` of length \(n\), using \(O(n)\) time; initialize an adjacency matrix `adjMat` of size \(n \times n\), using \(O(n^2)\) time.

<1><2><3><4><5>

Figure 9-7 Initialization, adding and removing edges, adding and removing vertices in adjacency matrix

The following is the implementation code for graphs represented using an adjacency matrix:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
graph_adjacency_matrix.py

    class GraphAdjMat:
        """Undirected graph class based on adjacency matrix"""

        def __init__(self, vertices: list[int], edges: list[list[int]]):
            """Constructor"""
            # Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
            self.vertices: list[int] = []
            # Adjacency matrix, where the row and column indices correspond to the "vertex index"
            self.adj_mat: list[list[int]] = []
            # Add vertices
            for val in vertices:
                self.add_vertex(val)
            # Add edges
            # Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for e in edges:
                self.add_edge(e[0], e[1])

        def size(self) -> int:
            """Get the number of vertices"""
            return len(self.vertices)

        def add_vertex(self, val: int):
            """Add vertex"""
            n = self.size()
            # Add the value of the new vertex to the vertex list
            self.vertices.append(val)
            # Add a row to the adjacency matrix
            new_row = [0] * n
            self.adj_mat.append(new_row)
            # Add a column to the adjacency matrix
            for row in self.adj_mat:
                row.append(0)

        def remove_vertex(self, index: int):
            """Remove vertex"""
            if index >= self.size():
                raise IndexError()
            # Remove the vertex at index from the vertex list
            self.vertices.pop(index)
            # Remove the row at index from the adjacency matrix
            self.adj_mat.pop(index)
            # Remove the column at index from the adjacency matrix
            for row in self.adj_mat:
                row.pop(index)

        def add_edge(self, i: int, j: int):
            """Add edge"""
            # Parameters i, j correspond to the vertices element indices
            # Handle index out of bounds and equality
            if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
                raise IndexError()
            # In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            self.adj_mat[i][j] = 1
            self.adj_mat[j][i] = 1

        def remove_edge(self, i: int, j: int):
            """Remove edge"""
            # Parameters i, j correspond to the vertices element indices
            # Handle index out of bounds and equality
            if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
                raise IndexError()
            self.adj_mat[i][j] = 0
            self.adj_mat[j][i] = 0

        def print(self):
            """Print adjacency matrix"""
            print("Vertex list =", self.vertices)
            print("Adjacency matrix =")
            print_matrix(self.adj_mat)

graph_adjacency_matrix.cpp

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
        vector<int> vertices;       // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        vector<vector<int>> adjMat; // Adjacency matrix, where the row and column indices correspond to the "vertex index"

      public:
        /* Constructor */
        GraphAdjMat(const vector<int> &vertices, const vector<vector<int>> &edges) {
            // Add vertex
            for (int val : vertices) {
                addVertex(val);
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for (const vector<int> &edge : edges) {
                addEdge(edge[0], edge[1]);
            }
        }

        /* Get the number of vertices */
        int size() const {
            return vertices.size();
        }

        /* Add vertex */
        void addVertex(int val) {
            int n = size();
            // Add the value of the new vertex to the vertex list
            vertices.push_back(val);
            // Add a row to the adjacency matrix
            adjMat.emplace_back(vector<int>(n, 0));
            // Add a column to the adjacency matrix
            for (vector<int> &row : adjMat) {
                row.push_back(0);
            }
        }

        /* Remove vertex */
        void removeVertex(int index) {
            if (index >= size()) {
                throw out_of_range("Vertex does not exist");
            }
            // Remove the vertex at index from the vertex list
            vertices.erase(vertices.begin() + index);
            // Remove the row at index from the adjacency matrix
            adjMat.erase(adjMat.begin() + index);
            // Remove the column at index from the adjacency matrix
            for (vector<int> &row : adjMat) {
                row.erase(row.begin() + index);
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        void addEdge(int i, int j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
                throw out_of_range("Vertex does not exist");
            }
            // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            adjMat[i][j] = 1;
            adjMat[j][i] = 1;
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        void removeEdge(int i, int j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
                throw out_of_range("Vertex does not exist");
            }
            adjMat[i][j] = 0;
            adjMat[j][i] = 0;
        }

        /* Print adjacency matrix */
        void print() {
            cout << "Vertex list = ";
            printVector(vertices);
            cout << "Adjacency matrix =" << endl;
            printVectorMatrix(adjMat);
        }
    };

graph_adjacency_matrix.java

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
        List<Integer> vertices; // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        List<List<Integer>> adjMat; // Adjacency matrix, where the row and column indices correspond to the "vertex index"

        /* Constructor */
        public GraphAdjMat(int[] vertices, int[][] edges) {
            this.vertices = new ArrayList<>();
            this.adjMat = new ArrayList<>();
            // Add vertex
            for (int val : vertices) {
                addVertex(val);
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for (int[] e : edges) {
                addEdge(e[0], e[1]);
            }
        }

        /* Get the number of vertices */
        public int size() {
            return vertices.size();
        }

        /* Add vertex */
        public void addVertex(int val) {
            int n = size();
            // Add the value of the new vertex to the vertex list
            vertices.add(val);
            // Add a row to the adjacency matrix
            List<Integer> newRow = new ArrayList<>(n);
            for (int j = 0; j < n; j++) {
                newRow.add(0);
            }
            adjMat.add(newRow);
            // Add a column to the adjacency matrix
            for (List<Integer> row : adjMat) {
                row.add(0);
            }
        }

        /* Remove vertex */
        public void removeVertex(int index) {
            if (index >= size())
                throw new IndexOutOfBoundsException();
            // Remove the vertex at index from the vertex list
            vertices.remove(index);
            // Remove the row at index from the adjacency matrix
            adjMat.remove(index);
            // Remove the column at index from the adjacency matrix
            for (List<Integer> row : adjMat) {
                row.remove(index);
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        public void addEdge(int i, int j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
                throw new IndexOutOfBoundsException();
            // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            adjMat.get(i).set(j, 1);
            adjMat.get(j).set(i, 1);
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        public void removeEdge(int i, int j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
                throw new IndexOutOfBoundsException();
            adjMat.get(i).set(j, 0);
            adjMat.get(j).set(i, 0);
        }

        /* Print adjacency matrix */
        public void print() {
            System.out.print("Vertex list = ");
            System.out.println(vertices);
            System.out.println("Adjacency matrix =");
            PrintUtil.printMatrix(adjMat);
        }
    }

graph_adjacency_matrix.cs

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
        List<int> vertices;     // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        List<List<int>> adjMat; // Adjacency matrix, where the row and column indices correspond to the "vertex index"

        /* Constructor */
        public GraphAdjMat(int[] vertices, int[][] edges) {
            this.vertices = [];
            this.adjMat = [];
            // Add vertex
            foreach (int val in vertices) {
                AddVertex(val);
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            foreach (int[] e in edges) {
                AddEdge(e[0], e[1]);
            }
        }

        /* Get the number of vertices */
        int Size() {
            return vertices.Count;
        }

        /* Add vertex */
        public void AddVertex(int val) {
            int n = Size();
            // Add the value of the new vertex to the vertex list
            vertices.Add(val);
            // Add a row to the adjacency matrix
            List<int> newRow = new(n);
            for (int j = 0; j < n; j++) {
                newRow.Add(0);
            }
            adjMat.Add(newRow);
            // Add a column to the adjacency matrix
            foreach (List<int> row in adjMat) {
                row.Add(0);
            }
        }

        /* Remove vertex */
        public void RemoveVertex(int index) {
            if (index >= Size())
                throw new IndexOutOfRangeException();
            // Remove the vertex at index from the vertex list
            vertices.RemoveAt(index);
            // Remove the row at index from the adjacency matrix
            adjMat.RemoveAt(index);
            // Remove the column at index from the adjacency matrix
            foreach (List<int> row in adjMat) {
                row.RemoveAt(index);
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        public void AddEdge(int i, int j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= Size() || j >= Size() || i == j)
                throw new IndexOutOfRangeException();
            // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            adjMat[i][j] = 1;
            adjMat[j][i] = 1;
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        public void RemoveEdge(int i, int j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= Size() || j >= Size() || i == j)
                throw new IndexOutOfRangeException();
            adjMat[i][j] = 0;
            adjMat[j][i] = 0;
        }

        /* Print adjacency matrix */
        public void Print() {
            Console.Write("Vertex list = ");
            PrintUtil.PrintList(vertices);
            Console.WriteLine("Adjacency matrix =");
            PrintUtil.PrintMatrix(adjMat);
        }
    }

graph_adjacency_matrix.go

    /* Undirected graph class based on adjacency matrix */
    type graphAdjMat struct {
        // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        vertices []int
        // Adjacency matrix, where the row and column indices correspond to the "vertex index"
        adjMat [][]int
    }

    /* Constructor */
    func newGraphAdjMat(vertices []int, edges [][]int) *graphAdjMat {
        // Add vertex
        n := len(vertices)
        adjMat := make([][]int, n)
        for i := range adjMat {
            adjMat[i] = make([]int, n)
        }
        // Initialize graph
        g := &graphAdjMat{
            vertices: vertices,
            adjMat:   adjMat,
        }
        // Add edge
        // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
        for i := range edges {
            g.addEdge(edges[i][0], edges[i][1])
        }
        return g
    }

    /* Get the number of vertices */
    func (g *graphAdjMat) size() int {
        return len(g.vertices)
    }

    /* Add vertex */
    func (g *graphAdjMat) addVertex(val int) {
        n := g.size()
        // Add the value of the new vertex to the vertex list
        g.vertices = append(g.vertices, val)
        // Add a row to the adjacency matrix
        newRow := make([]int, n)
        g.adjMat = append(g.adjMat, newRow)
        // Add a column to the adjacency matrix
        for i := range g.adjMat {
            g.adjMat[i] = append(g.adjMat[i], 0)
        }
    }

    /* Remove vertex */
    func (g *graphAdjMat) removeVertex(index int) {
        if index >= g.size() {
            return
        }
        // Remove the vertex at index from the vertex list
        g.vertices = append(g.vertices[:index], g.vertices[index+1:]...)
        // Remove the row at index from the adjacency matrix
        g.adjMat = append(g.adjMat[:index], g.adjMat[index+1:]...)
        // Remove the column at index from the adjacency matrix
        for i := range g.adjMat {
            g.adjMat[i] = append(g.adjMat[i][:index], g.adjMat[i][index+1:]...)
        }
    }

    /* Add edge */
    // Parameters i, j correspond to the vertices element indices
    func (g *graphAdjMat) addEdge(i, j int) {
        // Handle index out of bounds and equality
        if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
            fmt.Errorf("%s", "Index Out Of Bounds Exception")
        }
        // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
        g.adjMat[i][j] = 1
        g.adjMat[j][i] = 1
    }

    /* Remove edge */
    // Parameters i, j correspond to the vertices element indices
    func (g *graphAdjMat) removeEdge(i, j int) {
        // Handle index out of bounds and equality
        if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
            fmt.Errorf("%s", "Index Out Of Bounds Exception")
        }
        g.adjMat[i][j] = 0
        g.adjMat[j][i] = 0
    }

    /* Print adjacency matrix */
    func (g *graphAdjMat) print() {
        fmt.Printf("\tVertex list = %v\n", g.vertices)
        fmt.Printf("\tAdjacency matrix = \n")
        for i := range g.adjMat {
            fmt.Printf("\t\t\t%v\n", g.adjMat[i])
        }
    }

graph_adjacency_matrix.swift

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
        private var vertices: [Int] // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        private var adjMat: [[Int]] // Adjacency matrix, where the row and column indices correspond to the "vertex index"

        /* Constructor */
        init(vertices: [Int], edges: [[Int]]) {
            self.vertices = []
            adjMat = []
            // Add vertex
            for val in vertices {
                addVertex(val: val)
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for e in edges {
                addEdge(i: e[0], j: e[1])
            }
        }

        /* Get the number of vertices */
        func size() -> Int {
            vertices.count
        }

        /* Add vertex */
        func addVertex(val: Int) {
            let n = size()
            // Add the value of the new vertex to the vertex list
            vertices.append(val)
            // Add a row to the adjacency matrix
            let newRow = Array(repeating: 0, count: n)
            adjMat.append(newRow)
            // Add a column to the adjacency matrix
            for i in adjMat.indices {
                adjMat[i].append(0)
            }
        }

        /* Remove vertex */
        func removeVertex(index: Int) {
            if index >= size() {
                fatalError("Out of bounds")
            }
            // Remove the vertex at index from the vertex list
            vertices.remove(at: index)
            // Remove the row at index from the adjacency matrix
            adjMat.remove(at: index)
            // Remove the column at index from the adjacency matrix
            for i in adjMat.indices {
                adjMat[i].remove(at: index)
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        func addEdge(i: Int, j: Int) {
            // Handle index out of bounds and equality
            if i < 0 || j < 0 || i >= size() || j >= size() || i == j {
                fatalError("Out of bounds")
            }
            // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            adjMat[i][j] = 1
            adjMat[j][i] = 1
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        func removeEdge(i: Int, j: Int) {
            // Handle index out of bounds and equality
            if i < 0 || j < 0 || i >= size() || j >= size() || i == j {
                fatalError("Out of bounds")
            }
            adjMat[i][j] = 0
            adjMat[j][i] = 0
        }

        /* Print adjacency matrix */
        func print() {
            Swift.print("Vertex list = ", terminator: "")
            Swift.print(vertices)
            Swift.print("Adjacency matrix =")
            PrintUtil.printMatrix(matrix: adjMat)
        }
    }

graph_adjacency_matrix.js

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
        vertices; // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        adjMat; // Adjacency matrix, where the row and column indices correspond to the "vertex index"

        /* Constructor */
        constructor(vertices, edges) {
            this.vertices = [];
            this.adjMat = [];
            // Add vertex
            for (const val of vertices) {
                this.addVertex(val);
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for (const e of edges) {
                this.addEdge(e[0], e[1]);
            }
        }

        /* Get the number of vertices */
        size() {
            return this.vertices.length;
        }

        /* Add vertex */
        addVertex(val) {
            const n = this.size();
            // Add the value of the new vertex to the vertex list
            this.vertices.push(val);
            // Add a row to the adjacency matrix
            const newRow = [];
            for (let j = 0; j < n; j++) {
                newRow.push(0);
            }
            this.adjMat.push(newRow);
            // Add a column to the adjacency matrix
            for (const row of this.adjMat) {
                row.push(0);
            }
        }

        /* Remove vertex */
        removeVertex(index) {
            if (index >= this.size()) {
                throw new RangeError('Index Out Of Bounds Exception');
            }
            // Remove the vertex at index from the vertex list
            this.vertices.splice(index, 1);

            // Remove the row at index from the adjacency matrix
            this.adjMat.splice(index, 1);
            // Remove the column at index from the adjacency matrix
            for (const row of this.adjMat) {
                row.splice(index, 1);
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        addEdge(i, j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
                throw new RangeError('Index Out Of Bounds Exception');
            }
            // In undirected graph, adjacency matrix is symmetric about main diagonal, i.e., satisfies (i, j) === (j, i)
            this.adjMat[i][j] = 1;
            this.adjMat[j][i] = 1;
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        removeEdge(i, j) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
                throw new RangeError('Index Out Of Bounds Exception');
            }
            this.adjMat[i][j] = 0;
            this.adjMat[j][i] = 0;
        }

        /* Print adjacency matrix */
        print() {
            console.log('Vertex list = ', this.vertices);
            console.log('Adjacency matrix =', this.adjMat);
        }
    }

graph_adjacency_matrix.ts

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
        vertices: number[]; // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        adjMat: number[][]; // Adjacency matrix, where the row and column indices correspond to the "vertex index"

        /* Constructor */
        constructor(vertices: number[], edges: number[][]) {
            this.vertices = [];
            this.adjMat = [];
            // Add vertex
            for (const val of vertices) {
                this.addVertex(val);
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for (const e of edges) {
                this.addEdge(e[0], e[1]);
            }
        }

        /* Get the number of vertices */
        size(): number {
            return this.vertices.length;
        }

        /* Add vertex */
        addVertex(val: number): void {
            const n: number = this.size();
            // Add the value of the new vertex to the vertex list
            this.vertices.push(val);
            // Add a row to the adjacency matrix
            const newRow: number[] = [];
            for (let j: number = 0; j < n; j++) {
                newRow.push(0);
            }
            this.adjMat.push(newRow);
            // Add a column to the adjacency matrix
            for (const row of this.adjMat) {
                row.push(0);
            }
        }

        /* Remove vertex */
        removeVertex(index: number): void {
            if (index >= this.size()) {
                throw new RangeError('Index Out Of Bounds Exception');
            }
            // Remove the vertex at index from the vertex list
            this.vertices.splice(index, 1);

            // Remove the row at index from the adjacency matrix
            this.adjMat.splice(index, 1);
            // Remove the column at index from the adjacency matrix
            for (const row of this.adjMat) {
                row.splice(index, 1);
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        addEdge(i: number, j: number): void {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
                throw new RangeError('Index Out Of Bounds Exception');
            }
            // In undirected graph, adjacency matrix is symmetric about main diagonal, i.e., satisfies (i, j) === (j, i)
            this.adjMat[i][j] = 1;
            this.adjMat[j][i] = 1;
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        removeEdge(i: number, j: number): void {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
                throw new RangeError('Index Out Of Bounds Exception');
            }
            this.adjMat[i][j] = 0;
            this.adjMat[j][i] = 0;
        }

        /* Print adjacency matrix */
        print(): void {
            console.log('Vertex list = ', this.vertices);
            console.log('Adjacency matrix =', this.adjMat);
        }
    }

graph_adjacency_matrix.dart

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat {
      List<int> vertices = []; // Vertex elements, elements represent "vertex values", indices represent "vertex indices"
      List<List<int>> adjMat = []; // Adjacency matrix, where the row and column indices correspond to the "vertex index"

      /* Constructor */
      GraphAdjMat(List<int> vertices, List<List<int>> edges) {
        this.vertices = [];
        this.adjMat = [];
        // Add vertex
        for (int val in vertices) {
          addVertex(val);
        }
        // Add edge
        // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
        for (List<int> e in edges) {
          addEdge(e[0], e[1]);
        }
      }

      /* Get the number of vertices */
      int size() {
        return vertices.length;
      }

      /* Add vertex */
      void addVertex(int val) {
        int n = size();
        // Add the value of the new vertex to the vertex list
        vertices.add(val);
        // Add a row to the adjacency matrix
        List<int> newRow = List.filled(n, 0, growable: true);
        adjMat.add(newRow);
        // Add a column to the adjacency matrix
        for (List<int> row in adjMat) {
          row.add(0);
        }
      }

      /* Remove vertex */
      void removeVertex(int index) {
        if (index >= size()) {
          throw IndexError;
        }
        // Remove the vertex at index from the vertex list
        vertices.removeAt(index);
        // Remove the row at index from the adjacency matrix
        adjMat.removeAt(index);
        // Remove the column at index from the adjacency matrix
        for (List<int> row in adjMat) {
          row.removeAt(index);
        }
      }

      /* Add edge */
      // Parameters i, j correspond to the vertices element indices
      void addEdge(int i, int j) {
        // Handle index out of bounds and equality
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
          throw IndexError;
        }
        // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
      }

      /* Remove edge */
      // Parameters i, j correspond to the vertices element indices
      void removeEdge(int i, int j) {
        // Handle index out of bounds and equality
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
          throw IndexError;
        }
        adjMat[i][j] = 0;
        adjMat[j][i] = 0;
      }

      /* Print adjacency matrix */
      void printAdjMat() {
        print("Vertex list = $vertices");
        print("Adjacency matrix = ");
        printMatrix(adjMat);
      }
    }

graph_adjacency_matrix.rs

    /* Undirected graph type based on adjacency matrix */
    pub struct GraphAdjMat {
        // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        pub vertices: Vec<i32>,
        // Adjacency matrix, where the row and column indices correspond to the "vertex index"
        pub adj_mat: Vec<Vec<i32>>,
    }

    impl GraphAdjMat {
        /* Constructor */
        pub fn new(vertices: Vec<i32>, edges: Vec<[usize; 2]>) -> Self {
            let mut graph = GraphAdjMat {
                vertices: vec![],
                adj_mat: vec![],
            };
            // Add vertex
            for val in vertices {
                graph.add_vertex(val);
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for edge in edges {
                graph.add_edge(edge[0], edge[1])
            }

            graph
        }

        /* Get the number of vertices */
        pub fn size(&self) -> usize {
            self.vertices.len()
        }

        /* Add vertex */
        pub fn add_vertex(&mut self, val: i32) {
            let n = self.size();
            // Add the value of the new vertex to the vertex list
            self.vertices.push(val);
            // Add a row to the adjacency matrix
            self.adj_mat.push(vec![0; n]);
            // Add a column to the adjacency matrix
            for row in self.adj_mat.iter_mut() {
                row.push(0);
            }
        }

        /* Remove vertex */
        pub fn remove_vertex(&mut self, index: usize) {
            if index >= self.size() {
                panic!("index error")
            }
            // Remove the vertex at index from the vertex list
            self.vertices.remove(index);
            // Remove the row at index from the adjacency matrix
            self.adj_mat.remove(index);
            // Remove the column at index from the adjacency matrix
            for row in self.adj_mat.iter_mut() {
                row.remove(index);
            }
        }

        /* Add edge */
        pub fn add_edge(&mut self, i: usize, j: usize) {
            // Parameters i, j correspond to the vertices element indices
            // Handle index out of bounds and equality
            if i >= self.size() || j >= self.size() || i == j {
                panic!("index error")
            }
            // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            self.adj_mat[i][j] = 1;
            self.adj_mat[j][i] = 1;
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        pub fn remove_edge(&mut self, i: usize, j: usize) {
            // Parameters i, j correspond to the vertices element indices
            // Handle index out of bounds and equality
            if i >= self.size() || j >= self.size() || i == j {
                panic!("index error")
            }
            self.adj_mat[i][j] = 0;
            self.adj_mat[j][i] = 0;
        }

        /* Print adjacency matrix */
        pub fn print(&self) {
            println!("Vertex list = {:?}", self.vertices);
            println!("Adjacency matrix =");
            println!("[");
            for row in &self.adj_mat {
                println!("  {:?},", row);
            }
            println!("]")
        }
    }

graph_adjacency_matrix.c

    /* Undirected graph structure based on adjacency matrix */
    typedef struct {
        int vertices[MAX_SIZE];
        int adjMat[MAX_SIZE][MAX_SIZE];
        int size;
    } GraphAdjMat;

    /* Constructor */
    GraphAdjMat *newGraphAdjMat() {
        GraphAdjMat *graph = (GraphAdjMat *)malloc(sizeof(GraphAdjMat));
        graph->size = 0;
        for (int i = 0; i < MAX_SIZE; i++) {
            for (int j = 0; j < MAX_SIZE; j++) {
                graph->adjMat[i][j] = 0;
            }
        }
        return graph;
    }

    /* Destructor */
    void delGraphAdjMat(GraphAdjMat *graph) {
        free(graph);
    }

    /* Add vertex */
    void addVertex(GraphAdjMat *graph, int val) {
        if (graph->size == MAX_SIZE) {
            fprintf(stderr, "Graph vertex count has reached maximum\n");
            return;
        }
        // Add nth vertex and zero nth row and column
        int n = graph->size;
        graph->vertices[n] = val;
        for (int i = 0; i <= n; i++) {
            graph->adjMat[n][i] = graph->adjMat[i][n] = 0;
        }
        graph->size++;
    }

    /* Remove vertex */
    void removeVertex(GraphAdjMat *graph, int index) {
        if (index < 0 || index >= graph->size) {
            fprintf(stderr, "Vertex index out of bounds\n");
            return;
        }
        // Remove the vertex at index from the vertex list
        for (int i = index; i < graph->size - 1; i++) {
            graph->vertices[i] = graph->vertices[i + 1];
        }
        // Remove the row at index from the adjacency matrix
        for (int i = index; i < graph->size - 1; i++) {
            for (int j = 0; j < graph->size; j++) {
                graph->adjMat[i][j] = graph->adjMat[i + 1][j];
            }
        }
        // Remove the column at index from the adjacency matrix
        for (int i = 0; i < graph->size; i++) {
            for (int j = index; j < graph->size - 1; j++) {
                graph->adjMat[i][j] = graph->adjMat[i][j + 1];
            }
        }
        graph->size--;
    }

    /* Add edge */
    // Parameters i, j correspond to the vertices element indices
    void addEdge(GraphAdjMat *graph, int i, int j) {
        if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
            fprintf(stderr, "Edge index out of bounds or equal\n");
            return;
        }
        graph->adjMat[i][j] = 1;
        graph->adjMat[j][i] = 1;
    }

    /* Remove edge */
    // Parameters i, j correspond to the vertices element indices
    void removeEdge(GraphAdjMat *graph, int i, int j) {
        if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
            fprintf(stderr, "Edge index out of bounds or equal\n");
            return;
        }
        graph->adjMat[i][j] = 0;
        graph->adjMat[j][i] = 0;
    }

    /* Print adjacency matrix */
    void printGraphAdjMat(GraphAdjMat *graph) {
        printf("Vertex list = ");
        printArray(graph->vertices, graph->size);
        printf("Adjacency matrix =\n");
        for (int i = 0; i < graph->size; i++) {
            printArray(graph->adjMat[i], graph->size);
        }
    }

graph_adjacency_matrix.kt

    /* Undirected graph class based on adjacency matrix */
    class GraphAdjMat(vertices: IntArray, edges: Array<IntArray>) {
        val vertices = mutableListOf<Int>() // Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        val adjMat = mutableListOf<MutableList<Int>>() // Adjacency matrix, where the row and column indices correspond to the "vertex index"

        /* Constructor */
        init {
            // Add vertex
            for (vertex in vertices) {
                addVertex(vertex)
            }
            // Add edge
            // Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
            for (edge in edges) {
                addEdge(edge[0], edge[1])
            }
        }

        /* Get the number of vertices */
        fun size(): Int {
            return vertices.size
        }

        /* Add vertex */
        fun addVertex(_val: Int) {
            val n = size()
            // Add the value of the new vertex to the vertex list
            vertices.add(_val)
            // Add a row to the adjacency matrix
            val newRow = mutableListOf<Int>()
            for (j in 0..<n) {
                newRow.add(0)
            }
            adjMat.add(newRow)
            // Add a column to the adjacency matrix
            for (row in adjMat) {
                row.add(0)
            }
        }

        /* Remove vertex */
        fun removeVertex(index: Int) {
            if (index >= size())
                throw IndexOutOfBoundsException()
            // Remove the vertex at index from the vertex list
            vertices.removeAt(index)
            // Remove the row at index from the adjacency matrix
            adjMat.removeAt(index)
            // Remove the column at index from the adjacency matrix
            for (row in adjMat) {
                row.removeAt(index)
            }
        }

        /* Add edge */
        // Parameters i, j correspond to the vertices element indices
        fun addEdge(i: Int, j: Int) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
                throw IndexOutOfBoundsException()
            // In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
            adjMat[i][j] = 1
            adjMat[j][i] = 1
        }

        /* Remove edge */
        // Parameters i, j correspond to the vertices element indices
        fun removeEdge(i: Int, j: Int) {
            // Handle index out of bounds and equality
            if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
                throw IndexOutOfBoundsException()
            adjMat[i][j] = 0
            adjMat[j][i] = 0
        }

        /* Print adjacency matrix */
        fun print() {
            print("Vertex list = ")
            println(vertices)
            println("Adjacency matrix =")
            printMatrix(adjMat)
        }
    }

graph_adjacency_matrix.rb

    ### Undirected graph class based on adjacency matrix ###
    class GraphAdjMat
      def initialize(vertices, edges)
        ### Constructor ###
        # Vertex list, where the element represents the "vertex value" and the index represents the "vertex index"
        @vertices = []
        # Adjacency matrix, where the row and column indices correspond to the "vertex index"
        @adj_mat = []
        # Add vertex
        vertices.each { |val| add_vertex(val) }
        # Add edge
        # Note that the edges elements represent vertex indices, i.e., corresponding to the vertices element indices
        edges.each { |e| add_edge(e[0], e[1]) }
      end

      ### Get number of vertices ###
      def size
        @vertices.length
      end

      ### Add vertex ###
      def add_vertex(val)
        n = size
        # Add the value of the new vertex to the vertex list
        @vertices << val
        # Add a row to the adjacency matrix
        new_row = Array.new(n, 0)
        @adj_mat << new_row
        # Add a column to the adjacency matrix
        @adj_mat.each { |row| row << 0 }
      end

      ### Delete vertex ###
      def remove_vertex(index)
        raise IndexError if index >= size

        # Remove the vertex at index from the vertex list
        @vertices.delete_at(index)
        # Remove the row at index from the adjacency matrix
        @adj_mat.delete_at(index)
        # Remove the column at index from the adjacency matrix
        @adj_mat.each { |row| row.delete_at(index) }
      end

      ### Add edge ###
      def add_edge(i, j)
        # Parameters i, j correspond to the vertices element indices
        # Handle index out of bounds and equality
        if i < 0 || j < 0 || i >= size || j >= size || i == j
          raise IndexError
        end
        # In an undirected graph, the adjacency matrix is symmetric about the main diagonal, i.e., (i, j) == (j, i)
        @adj_mat[i][j] = 1
        @adj_mat[j][i] = 1
      end

      ### Delete edge ###
      def remove_edge(i, j)
        # Parameters i, j correspond to the vertices element indices
        # Handle index out of bounds and equality
        if i < 0 || j < 0 || i >= size || j >= size || i == j
          raise IndexError
        end
        @adj_mat[i][j] = 0
        @adj_mat[j][i] = 0
      end

      ### Print adjacency matrix ###
      def __print__
        puts "Vertex list = #{@vertices}"
        puts 'Adjacency matrix ='
        print_matrix(@adj_mat)
      end
    end

## 9.2.2 Implementation Based on Adjacency List

Given an undirected graph with a total of \(n\) vertices and \(m\) edges, the various operations can be implemented as shown in Figure 9-8.

- Adding an edge: Add the edge at the end of the corresponding vertex's linked list, using \(O(1)\) time. Since it is an undirected graph, edges in both directions need to be added simultaneously.
- Removing an edge: Find and remove the specified edge in the corresponding vertex's linked list, using \(O(m)\) time. In an undirected graph, edges in both directions need to be removed simultaneously.
- Adding a vertex: Add a linked list to the adjacency list, with the new vertex as the head node, using \(O(1)\) time.
- Removing a vertex: Traverse the entire adjacency list and remove all edges containing the specified vertex, using \(O(n + m)\) time.
- Initialization: Create \(n\) vertices and \(2m\) edges in the adjacency list, using \(O(n + m)\) time.

<1><2><3><4><5>

Figure 9-8 Initialization, adding and removing edges, adding and removing vertices in adjacency list

The following code shows the adjacency list implementation. Compared with Figure 9-8, the actual code differs in the following ways.

- For convenience in adding and removing vertices, and to simplify the code, we use lists (dynamic arrays) instead of linked lists.
- A hash table is used to store the adjacency list, where `key` is the vertex instance and `value` is the list (linked list) of adjacent vertices for that vertex.

Additionally, we use the `Vertex` class to represent vertices in the adjacency list for the following reason: if we used list indices to distinguish different vertices, as with adjacency matrices, then to delete the vertex at index \(i\), we would need to traverse the entire adjacency list and decrement all indices greater than \(i\) by \(1\), which is very inefficient. However, if each vertex is a unique `Vertex` instance, deleting one vertex does not require modifying the others.

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
graph_adjacency_list.py

    class GraphAdjList:
        """Undirected graph class based on adjacency list"""

        def __init__(self, edges: list[list[Vertex]]):
            """Constructor"""
            # Adjacency list, key: vertex, value: all adjacent vertices of that vertex
            self.adj_list = dict[Vertex, list[Vertex]]()
            # Add all vertices and edges
            for edge in edges:
                self.add_vertex(edge[0])
                self.add_vertex(edge[1])
                self.add_edge(edge[0], edge[1])

        def size(self) -> int:
            """Get the number of vertices"""
            return len(self.adj_list)

        def add_edge(self, vet1: Vertex, vet2: Vertex):
            """Add edge"""
            if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
                raise ValueError()
            # Add edge vet1 - vet2
            self.adj_list[vet1].append(vet2)
            self.adj_list[vet2].append(vet1)

        def remove_edge(self, vet1: Vertex, vet2: Vertex):
            """Remove edge"""
            if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
                raise ValueError()
            # Remove edge vet1 - vet2
            self.adj_list[vet1].remove(vet2)
            self.adj_list[vet2].remove(vet1)

        def add_vertex(self, vet: Vertex):
            """Add vertex"""
            if vet in self.adj_list:
                return
            # Add a new linked list in the adjacency list
            self.adj_list[vet] = []

        def remove_vertex(self, vet: Vertex):
            """Remove vertex"""
            if vet not in self.adj_list:
                raise ValueError()
            # Remove the linked list corresponding to vertex vet in the adjacency list
            self.adj_list.pop(vet)
            # Traverse the linked lists of other vertices and remove all edges containing vet
            for vertex in self.adj_list:
                if vet in self.adj_list[vertex]:
                    self.adj_list[vertex].remove(vet)

        def print(self):
            """Print adjacency list"""
            print("Adjacency list =")
            for vertex in self.adj_list:
                tmp = [v.val for v in self.adj_list[vertex]]
                print(f"{vertex.val}: {tmp},")

graph_adjacency_list.cpp

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
      public:
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        unordered_map<Vertex *, vector<Vertex *>> adjList;

        /* Remove specified node from vector */
        void remove(vector<Vertex *> &vec, Vertex *vet) {
            for (int i = 0; i < vec.size(); i++) {
                if (vec[i] == vet) {
                    vec.erase(vec.begin() + i);
                    break;
                }
            }
        }

        /* Constructor */
        GraphAdjList(const vector<vector<Vertex *>> &edges) {
            // Add all vertices and edges
            for (const vector<Vertex *> &edge : edges) {
                addVertex(edge[0]);
                addVertex(edge[1]);
                addEdge(edge[0], edge[1]);
            }
        }

        /* Get the number of vertices */
        int size() {
            return adjList.size();
        }

        /* Add edge */
        void addEdge(Vertex *vet1, Vertex *vet2) {
            if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
                throw invalid_argument("Vertex does not exist");
            // Add edge vet1 - vet2
            adjList[vet1].push_back(vet2);
            adjList[vet2].push_back(vet1);
        }

        /* Remove edge */
        void removeEdge(Vertex *vet1, Vertex *vet2) {
            if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
                throw invalid_argument("Vertex does not exist");
            // Remove edge vet1 - vet2
            remove(adjList[vet1], vet2);
            remove(adjList[vet2], vet1);
        }

        /* Add vertex */
        void addVertex(Vertex *vet) {
            if (adjList.count(vet))
                return;
            // Add a new linked list in the adjacency list
            adjList[vet] = vector<Vertex *>();
        }

        /* Remove vertex */
        void removeVertex(Vertex *vet) {
            if (!adjList.count(vet))
                throw invalid_argument("Vertex does not exist");
            // Remove the linked list corresponding to vertex vet in the adjacency list
            adjList.erase(vet);
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for (auto &adj : adjList) {
                remove(adj.second, vet);
            }
        }

        /* Print adjacency list */
        void print() {
            cout << "Adjacency list =" << endl;
            for (auto &adj : adjList) {
                const auto &key = adj.first;
                const auto &vec = adj.second;
                cout << key->val << ": ";
                printVector(vetsToVals(vec));
            }
        }
    };

graph_adjacency_list.java

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        Map<Vertex, List<Vertex>> adjList;

        /* Constructor */
        public GraphAdjList(Vertex[][] edges) {
            this.adjList = new HashMap<>();
            // Add all vertices and edges
            for (Vertex[] edge : edges) {
                addVertex(edge[0]);
                addVertex(edge[1]);
                addEdge(edge[0], edge[1]);
            }
        }

        /* Get the number of vertices */
        public int size() {
            return adjList.size();
        }

        /* Add edge */
        public void addEdge(Vertex vet1, Vertex vet2) {
            if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
                throw new IllegalArgumentException();
            // Add edge vet1 - vet2
            adjList.get(vet1).add(vet2);
            adjList.get(vet2).add(vet1);
        }

        /* Remove edge */
        public void removeEdge(Vertex vet1, Vertex vet2) {
            if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
                throw new IllegalArgumentException();
            // Remove edge vet1 - vet2
            adjList.get(vet1).remove(vet2);
            adjList.get(vet2).remove(vet1);
        }

        /* Add vertex */
        public void addVertex(Vertex vet) {
            if (adjList.containsKey(vet))
                return;
            // Add a new linked list in the adjacency list
            adjList.put(vet, new ArrayList<>());
        }

        /* Remove vertex */
        public void removeVertex(Vertex vet) {
            if (!adjList.containsKey(vet))
                throw new IllegalArgumentException();
            // Remove the linked list corresponding to vertex vet in the adjacency list
            adjList.remove(vet);
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for (List<Vertex> list : adjList.values()) {
                list.remove(vet);
            }
        }

        /* Print adjacency list */
        public void print() {
            System.out.println("Adjacency list =");
            for (Map.Entry<Vertex, List<Vertex>> pair : adjList.entrySet()) {
                List<Integer> tmp = new ArrayList<>();
                for (Vertex vertex : pair.getValue())
                    tmp.add(vertex.val);
                System.out.println(pair.getKey().val + ": " + tmp + ",");
            }
        }
    }

graph_adjacency_list.cs

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        public Dictionary<Vertex, List<Vertex>> adjList;

        /* Constructor */
        public GraphAdjList(Vertex[][] edges) {
            adjList = [];
            // Add all vertices and edges
            foreach (Vertex[] edge in edges) {
                AddVertex(edge[0]);
                AddVertex(edge[1]);
                AddEdge(edge[0], edge[1]);
            }
        }

        /* Get the number of vertices */
        int Size() {
            return adjList.Count;
        }

        /* Add edge */
        public void AddEdge(Vertex vet1, Vertex vet2) {
            if (!adjList.ContainsKey(vet1) || !adjList.ContainsKey(vet2) || vet1 == vet2)
                throw new InvalidOperationException();
            // Add edge vet1 - vet2
            adjList[vet1].Add(vet2);
            adjList[vet2].Add(vet1);
        }

        /* Remove edge */
        public void RemoveEdge(Vertex vet1, Vertex vet2) {
            if (!adjList.ContainsKey(vet1) || !adjList.ContainsKey(vet2) || vet1 == vet2)
                throw new InvalidOperationException();
            // Remove edge vet1 - vet2
            adjList[vet1].Remove(vet2);
            adjList[vet2].Remove(vet1);
        }

        /* Add vertex */
        public void AddVertex(Vertex vet) {
            if (adjList.ContainsKey(vet))
                return;
            // Add a new linked list in the adjacency list
            adjList.Add(vet, []);
        }

        /* Remove vertex */
        public void RemoveVertex(Vertex vet) {
            if (!adjList.ContainsKey(vet))
                throw new InvalidOperationException();
            // Remove the linked list corresponding to vertex vet in the adjacency list
            adjList.Remove(vet);
            // Traverse the linked lists of other vertices and remove all edges containing vet
            foreach (List<Vertex> list in adjList.Values) {
                list.Remove(vet);
            }
        }

        /* Print adjacency list */
        public void Print() {
            Console.WriteLine("Adjacency list =");
            foreach (KeyValuePair<Vertex, List<Vertex>> pair in adjList) {
                List<int> tmp = [];
                foreach (Vertex vertex in pair.Value)
                    tmp.Add(vertex.val);
                Console.WriteLine(pair.Key.val + ": [" + string.Join(", ", tmp) + "],");
            }
        }
    }

graph_adjacency_list.go

    /* Undirected graph class based on adjacency list */
    type graphAdjList struct {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        adjList map[Vertex][]Vertex
    }

    /* Constructor */
    func newGraphAdjList(edges [][]Vertex) *graphAdjList {
        g := &graphAdjList{
            adjList: make(map[Vertex][]Vertex),
        }
        // Add all vertices and edges
        for _, edge := range edges {
            g.addVertex(edge[0])
            g.addVertex(edge[1])
            g.addEdge(edge[0], edge[1])
        }
        return g
    }

    /* Get the number of vertices */
    func (g *graphAdjList) size() int {
        return len(g.adjList)
    }

    /* Add edge */
    func (g *graphAdjList) addEdge(vet1 Vertex, vet2 Vertex) {
        _, ok1 := g.adjList[vet1]
        _, ok2 := g.adjList[vet2]
        if !ok1 || !ok2 || vet1 == vet2 {
            panic("error")
        }
        // Add edge vet1 - vet2, add anonymous struct{},
        g.adjList[vet1] = append(g.adjList[vet1], vet2)
        g.adjList[vet2] = append(g.adjList[vet2], vet1)
    }

    /* Remove edge */
    func (g *graphAdjList) removeEdge(vet1 Vertex, vet2 Vertex) {
        _, ok1 := g.adjList[vet1]
        _, ok2 := g.adjList[vet2]
        if !ok1 || !ok2 || vet1 == vet2 {
            panic("error")
        }
        // Remove edge vet1 - vet2
        g.adjList[vet1] = DeleteSliceElms(g.adjList[vet1], vet2)
        g.adjList[vet2] = DeleteSliceElms(g.adjList[vet2], vet1)
    }

    /* Add vertex */
    func (g *graphAdjList) addVertex(vet Vertex) {
        _, ok := g.adjList[vet]
        if ok {
            return
        }
        // Add a new linked list in the adjacency list
        g.adjList[vet] = make([]Vertex, 0)
    }

    /* Remove vertex */
    func (g *graphAdjList) removeVertex(vet Vertex) {
        _, ok := g.adjList[vet]
        if !ok {
            panic("error")
        }
        // Remove the linked list corresponding to vertex vet in the adjacency list
        delete(g.adjList, vet)
        // Traverse the linked lists of other vertices and remove all edges containing vet
        for v, list := range g.adjList {
            g.adjList[v] = DeleteSliceElms(list, vet)
        }
    }

    /* Print adjacency list */
    func (g *graphAdjList) print() {
        var builder strings.Builder
        fmt.Printf("Adjacency list = \n")
        for k, v := range g.adjList {
            builder.WriteString("\t\t" + strconv.Itoa(k.Val) + ": ")
            for _, vet := range v {
                builder.WriteString(strconv.Itoa(vet.Val) + " ")
            }
            fmt.Println(builder.String())
            builder.Reset()
        }
    }

graph_adjacency_list.swift

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        public private(set) var adjList: [Vertex: [Vertex]]

        /* Constructor */
        public init(edges: [[Vertex]]) {
            adjList = [:]
            // Add all vertices and edges
            for edge in edges {
                addVertex(vet: edge[0])
                addVertex(vet: edge[1])
                addEdge(vet1: edge[0], vet2: edge[1])
            }
        }

        /* Get the number of vertices */
        public func size() -> Int {
            adjList.count
        }

        /* Add edge */
        public func addEdge(vet1: Vertex, vet2: Vertex) {
            if adjList[vet1] == nil || adjList[vet2] == nil || vet1 == vet2 {
                fatalError("Invalid parameter")
            }
            // Add edge vet1 - vet2
            adjList[vet1]?.append(vet2)
            adjList[vet2]?.append(vet1)
        }

        /* Remove edge */
        public func removeEdge(vet1: Vertex, vet2: Vertex) {
            if adjList[vet1] == nil || adjList[vet2] == nil || vet1 == vet2 {
                fatalError("Invalid parameter")
            }
            // Remove edge vet1 - vet2
            adjList[vet1]?.removeAll { $0 == vet2 }
            adjList[vet2]?.removeAll { $0 == vet1 }
        }

        /* Add vertex */
        public func addVertex(vet: Vertex) {
            if adjList[vet] != nil {
                return
            }
            // Add a new linked list in the adjacency list
            adjList[vet] = []
        }

        /* Remove vertex */
        public func removeVertex(vet: Vertex) {
            if adjList[vet] == nil {
                fatalError("Invalid parameter")
            }
            // Remove the linked list corresponding to vertex vet in the adjacency list
            adjList.removeValue(forKey: vet)
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for key in adjList.keys {
                adjList[key]?.removeAll { $0 == vet }
            }
        }

        /* Print adjacency list */
        public func print() {
            Swift.print("Adjacency list =")
            for (vertex, list) in adjList {
                let list = list.map { $0.val }
                Swift.print("\(vertex.val): \(list),")
            }
        }
    }

graph_adjacency_list.js

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        adjList;

        /* Constructor */
        constructor(edges) {
            this.adjList = new Map();
            // Add all vertices and edges
            for (const edge of edges) {
                this.addVertex(edge[0]);
                this.addVertex(edge[1]);
                this.addEdge(edge[0], edge[1]);
            }
        }

        /* Get the number of vertices */
        size() {
            return this.adjList.size;
        }

        /* Add edge */
        addEdge(vet1, vet2) {
            if (
                !this.adjList.has(vet1) ||
                !this.adjList.has(vet2) ||
                vet1 === vet2
            ) {
                throw new Error('Illegal Argument Exception');
            }
            // Add edge vet1 - vet2
            this.adjList.get(vet1).push(vet2);
            this.adjList.get(vet2).push(vet1);
        }

        /* Remove edge */
        removeEdge(vet1, vet2) {
            if (
                !this.adjList.has(vet1) ||
                !this.adjList.has(vet2) ||
                vet1 === vet2 ||
                this.adjList.get(vet1).indexOf(vet2) === -1
            ) {
                throw new Error('Illegal Argument Exception');
            }
            // Remove edge vet1 - vet2
            this.adjList.get(vet1).splice(this.adjList.get(vet1).indexOf(vet2), 1);
            this.adjList.get(vet2).splice(this.adjList.get(vet2).indexOf(vet1), 1);
        }

        /* Add vertex */
        addVertex(vet) {
            if (this.adjList.has(vet)) return;
            // Add a new linked list in the adjacency list
            this.adjList.set(vet, []);
        }

        /* Remove vertex */
        removeVertex(vet) {
            if (!this.adjList.has(vet)) {
                throw new Error('Illegal Argument Exception');
            }
            // Remove the linked list corresponding to vertex vet in the adjacency list
            this.adjList.delete(vet);
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for (const set of this.adjList.values()) {
                const index = set.indexOf(vet);
                if (index > -1) {
                    set.splice(index, 1);
                }
            }
        }

        /* Print adjacency list */
        print() {
            console.log('Adjacency list =');
            for (const [key, value] of this.adjList) {
                const tmp = [];
                for (const vertex of value) {
                    tmp.push(vertex.val);
                }
                console.log(key.val + ': ' + tmp.join());
            }
        }
    }

graph_adjacency_list.ts

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        adjList: Map<Vertex, Vertex[]>;

        /* Constructor */
        constructor(edges: Vertex[][]) {
            this.adjList = new Map();
            // Add all vertices and edges
            for (const edge of edges) {
                this.addVertex(edge[0]);
                this.addVertex(edge[1]);
                this.addEdge(edge[0], edge[1]);
            }
        }

        /* Get the number of vertices */
        size(): number {
            return this.adjList.size;
        }

        /* Add edge */
        addEdge(vet1: Vertex, vet2: Vertex): void {
            if (
                !this.adjList.has(vet1) ||
                !this.adjList.has(vet2) ||
                vet1 === vet2
            ) {
                throw new Error('Illegal Argument Exception');
            }
            // Add edge vet1 - vet2
            this.adjList.get(vet1).push(vet2);
            this.adjList.get(vet2).push(vet1);
        }

        /* Remove edge */
        removeEdge(vet1: Vertex, vet2: Vertex): void {
            if (
                !this.adjList.has(vet1) ||
                !this.adjList.has(vet2) ||
                vet1 === vet2 ||
                this.adjList.get(vet1).indexOf(vet2) === -1
            ) {
                throw new Error('Illegal Argument Exception');
            }
            // Remove edge vet1 - vet2
            this.adjList.get(vet1).splice(this.adjList.get(vet1).indexOf(vet2), 1);
            this.adjList.get(vet2).splice(this.adjList.get(vet2).indexOf(vet1), 1);
        }

        /* Add vertex */
        addVertex(vet: Vertex): void {
            if (this.adjList.has(vet)) return;
            // Add a new linked list in the adjacency list
            this.adjList.set(vet, []);
        }

        /* Remove vertex */
        removeVertex(vet: Vertex): void {
            if (!this.adjList.has(vet)) {
                throw new Error('Illegal Argument Exception');
            }
            // Remove the linked list corresponding to vertex vet in the adjacency list
            this.adjList.delete(vet);
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for (const set of this.adjList.values()) {
                const index: number = set.indexOf(vet);
                if (index > -1) {
                    set.splice(index, 1);
                }
            }
        }

        /* Print adjacency list */
        print(): void {
            console.log('Adjacency list =');
            for (const [key, value] of this.adjList.entries()) {
                const tmp = [];
                for (const vertex of value) {
                    tmp.push(vertex.val);
                }
                console.log(key.val + ': ' + tmp.join());
            }
        }
    }

graph_adjacency_list.dart

    /* Undirected graph class based on adjacency list */
    class GraphAdjList {
      // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
      Map<Vertex, List<Vertex>> adjList = {};

      /* Constructor */
      GraphAdjList(List<List<Vertex>> edges) {
        for (List<Vertex> edge in edges) {
          addVertex(edge[0]);
          addVertex(edge[1]);
          addEdge(edge[0], edge[1]);
        }
      }

      /* Get the number of vertices */
      int size() {
        return adjList.length;
      }

      /* Add edge */
      void addEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) ||
            !adjList.containsKey(vet2) ||
            vet1 == vet2) {
          throw ArgumentError;
        }
        // Add edge vet1 - vet2
        adjList[vet1]!.add(vet2);
        adjList[vet2]!.add(vet1);
      }

      /* Remove edge */
      void removeEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) ||
            !adjList.containsKey(vet2) ||
            vet1 == vet2) {
          throw ArgumentError;
        }
        // Remove edge vet1 - vet2
        adjList[vet1]!.remove(vet2);
        adjList[vet2]!.remove(vet1);
      }

      /* Add vertex */
      void addVertex(Vertex vet) {
        if (adjList.containsKey(vet)) return;
        // Add a new linked list in the adjacency list
        adjList[vet] = [];
      }

      /* Remove vertex */
      void removeVertex(Vertex vet) {
        if (!adjList.containsKey(vet)) {
          throw ArgumentError;
        }
        // Remove the linked list corresponding to vertex vet in the adjacency list
        adjList.remove(vet);
        // Traverse the linked lists of other vertices and remove all edges containing vet
        adjList.forEach((key, value) {
          value.remove(vet);
        });
      }

      /* Print adjacency list */
      void printAdjList() {
        print("Adjacency list =");
        adjList.forEach((key, value) {
          List<int> tmp = [];
          for (Vertex vertex in value) {
            tmp.add(vertex.val);
          }
          print("${key.val}: $tmp,");
        });
      }
    }

graph_adjacency_list.rs

    /* Undirected graph type based on adjacency list */
    pub struct GraphAdjList {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        pub adj_list: HashMap<Vertex, Vec<Vertex>>, // maybe HashSet<Vertex> for value part is better?
    }

    impl GraphAdjList {
        /* Constructor */
        pub fn new(edges: Vec<[Vertex; 2]>) -> Self {
            let mut graph = GraphAdjList {
                adj_list: HashMap::new(),
            };
            // Add all vertices and edges
            for edge in edges {
                graph.add_vertex(edge[0]);
                graph.add_vertex(edge[1]);
                graph.add_edge(edge[0], edge[1]);
            }

            graph
        }

        /* Get the number of vertices */
        #[allow(unused)]
        pub fn size(&self) -> usize {
            self.adj_list.len()
        }

        /* Add edge */
        pub fn add_edge(&mut self, vet1: Vertex, vet2: Vertex) {
            if vet1 == vet2 {
                panic!("value error");
            }
            // Add edge vet1 - vet2
            self.adj_list.entry(vet1).or_default().push(vet2);
            self.adj_list.entry(vet2).or_default().push(vet1);
        }

        /* Remove edge */
        #[allow(unused)]
        pub fn remove_edge(&mut self, vet1: Vertex, vet2: Vertex) {
            if vet1 == vet2 {
                panic!("value error");
            }
            // Remove edge vet1 - vet2
            self.adj_list
                .entry(vet1)
                .and_modify(|v| v.retain(|&e| e != vet2));
            self.adj_list
                .entry(vet2)
                .and_modify(|v| v.retain(|&e| e != vet1));
        }

        /* Add vertex */
        pub fn add_vertex(&mut self, vet: Vertex) {
            if self.adj_list.contains_key(&vet) {
                return;
            }
            // Add a new linked list in the adjacency list
            self.adj_list.insert(vet, vec![]);
        }

        /* Remove vertex */
        #[allow(unused)]
        pub fn remove_vertex(&mut self, vet: Vertex) {
            // Remove the linked list corresponding to vertex vet in the adjacency list
            self.adj_list.remove(&vet);
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for list in self.adj_list.values_mut() {
                list.retain(|&v| v != vet);
            }
        }

        /* Print adjacency list */
        pub fn print(&self) {
            println!("Adjacency list =");
            for (vertex, list) in &self.adj_list {
                let list = list.iter().map(|vertex| vertex.val).collect::<Vec<i32>>();
                println!("{}: {:?},", vertex.val, list);
            }
        }
    }

graph_adjacency_list.c

    /* Node structure */
    typedef struct AdjListNode {
        Vertex *vertex;           // Vertex
        struct AdjListNode *next; // Successor node
    } AdjListNode;

    /* Find node corresponding to vertex */
    AdjListNode *findNode(GraphAdjList *graph, Vertex *vet) {
        for (int i = 0; i < graph->size; i++) {
            if (graph->heads[i]->vertex == vet) {
                return graph->heads[i];
            }
        }
        return NULL;
    }

    /* Add edge helper function */
    void addEdgeHelper(AdjListNode *head, Vertex *vet) {
        AdjListNode *node = (AdjListNode *)malloc(sizeof(AdjListNode));
        node->vertex = vet;
        // Head insertion
        node->next = head->next;
        head->next = node;
    }

    /* Remove edge helper function */
    void removeEdgeHelper(AdjListNode *head, Vertex *vet) {
        AdjListNode *pre = head;
        AdjListNode *cur = head->next;
        // Search for node corresponding to vet in list
        while (cur != NULL && cur->vertex != vet) {
            pre = cur;
            cur = cur->next;
        }
        if (cur == NULL)
            return;
        // Remove node corresponding to vet from list
        pre->next = cur->next;
        // Free memory
        free(cur);
    }

    /* Undirected graph class based on adjacency list */
    typedef struct {
        AdjListNode *heads[MAX_SIZE]; // Node array
        int size;                     // Node count
    } GraphAdjList;

    /* Constructor */
    GraphAdjList *newGraphAdjList() {
        GraphAdjList *graph = (GraphAdjList *)malloc(sizeof(GraphAdjList));
        if (!graph) {
            return NULL;
        }
        graph->size = 0;
        for (int i = 0; i < MAX_SIZE; i++) {
            graph->heads[i] = NULL;
        }
        return graph;
    }

    /* Destructor */
    void delGraphAdjList(GraphAdjList *graph) {
        for (int i = 0; i < graph->size; i++) {
            AdjListNode *cur = graph->heads[i];
            while (cur != NULL) {
                AdjListNode *next = cur->next;
                if (cur != graph->heads[i]) {
                    free(cur);
                }
                cur = next;
            }
            free(graph->heads[i]->vertex);
            free(graph->heads[i]);
        }
        free(graph);
    }

    /* Find node corresponding to vertex */
    AdjListNode *findNode(GraphAdjList *graph, Vertex *vet) {
        for (int i = 0; i < graph->size; i++) {
            if (graph->heads[i]->vertex == vet) {
                return graph->heads[i];
            }
        }
        return NULL;
    }

    /* Add edge */
    void addEdge(GraphAdjList *graph, Vertex *vet1, Vertex *vet2) {
        AdjListNode *head1 = findNode(graph, vet1);
        AdjListNode *head2 = findNode(graph, vet2);
        assert(head1 != NULL && head2 != NULL && head1 != head2);
        // Add edge vet1 - vet2
        addEdgeHelper(head1, vet2);
        addEdgeHelper(head2, vet1);
    }

    /* Remove edge */
    void removeEdge(GraphAdjList *graph, Vertex *vet1, Vertex *vet2) {
        AdjListNode *head1 = findNode(graph, vet1);
        AdjListNode *head2 = findNode(graph, vet2);
        assert(head1 != NULL && head2 != NULL);
        // Remove edge vet1 - vet2
        removeEdgeHelper(head1, head2->vertex);
        removeEdgeHelper(head2, head1->vertex);
    }

    /* Add vertex */
    void addVertex(GraphAdjList *graph, Vertex *vet) {
        assert(graph != NULL && graph->size < MAX_SIZE);
        AdjListNode *head = (AdjListNode *)malloc(sizeof(AdjListNode));
        head->vertex = vet;
        head->next = NULL;
        // Add a new linked list in the adjacency list
        graph->heads[graph->size++] = head;
    }

    /* Remove vertex */
    void removeVertex(GraphAdjList *graph, Vertex *vet) {
        AdjListNode *node = findNode(graph, vet);
        assert(node != NULL);
        // Remove the linked list corresponding to vertex vet in the adjacency list
        AdjListNode *cur = node, *pre = NULL;
        while (cur) {
            pre = cur;
            cur = cur->next;
            free(pre);
        }
        // Traverse the linked lists of other vertices and remove all edges containing vet
        for (int i = 0; i < graph->size; i++) {
            cur = graph->heads[i];
            pre = NULL;
            while (cur) {
                pre = cur;
                cur = cur->next;
                if (cur && cur->vertex == vet) {
                    pre->next = cur->next;
                    free(cur);
                    break;
                }
            }
        }
        // Move vertices after this vertex forward to fill gap
        int i;
        for (i = 0; i < graph->size; i++) {
            if (graph->heads[i] == node)
                break;
        }
        for (int j = i; j < graph->size - 1; j++) {
            graph->heads[j] = graph->heads[j + 1];
        }
        graph->size--;
        free(vet);
    }

graph_adjacency_list.kt

    /* Undirected graph class based on adjacency list */
    class GraphAdjList(edges: Array<Array<Vertex?>>) {
        // Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        val adjList = HashMap<Vertex, MutableList<Vertex>>()

        /* Constructor */
        init {
            // Add all vertices and edges
            for (edge in edges) {
                addVertex(edge[0]!!)
                addVertex(edge[1]!!)
                addEdge(edge[0]!!, edge[1]!!)
            }
        }

        /* Get the number of vertices */
        fun size(): Int {
            return adjList.size
        }

        /* Add edge */
        fun addEdge(vet1: Vertex, vet2: Vertex) {
            if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
                throw IllegalArgumentException()
            // Add edge vet1 - vet2
            adjList[vet1]?.add(vet2)
            adjList[vet2]?.add(vet1)
        }

        /* Remove edge */
        fun removeEdge(vet1: Vertex, vet2: Vertex) {
            if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
                throw IllegalArgumentException()
            // Remove edge vet1 - vet2
            adjList[vet1]?.remove(vet2)
            adjList[vet2]?.remove(vet1)
        }

        /* Add vertex */
        fun addVertex(vet: Vertex) {
            if (adjList.containsKey(vet))
                return
            // Add a new linked list in the adjacency list
            adjList[vet] = mutableListOf()
        }

        /* Remove vertex */
        fun removeVertex(vet: Vertex) {
            if (!adjList.containsKey(vet))
                throw IllegalArgumentException()
            // Remove the linked list corresponding to vertex vet in the adjacency list
            adjList.remove(vet)
            // Traverse the linked lists of other vertices and remove all edges containing vet
            for (list in adjList.values) {
                list.remove(vet)
            }
        }

        /* Print adjacency list */
        fun print() {
            println("Adjacency list =")
            for (pair in adjList.entries) {
                val tmp = mutableListOf<Int>()
                for (vertex in pair.value) {
                    tmp.add(vertex._val)
                }
                println("${pair.key._val}: $tmp,")
            }
        }
    }

graph_adjacency_list.rb

    ### Undirected graph class based on adjacency list ###
    class GraphAdjList
      attr_reader :adj_list

      ### Constructor ###
      def initialize(edges)
        # Adjacency list, key: vertex, value: all adjacent vertices of that vertex
        @adj_list = {}
        # Add all vertices and edges
        for edge in edges
          add_vertex(edge[0])
          add_vertex(edge[1])
          add_edge(edge[0], edge[1])
        end
      end

      ### Get number of vertices ###
      def size
        @adj_list.length
      end

      ### Add edge ###
      def add_edge(vet1, vet2)
        raise ArgumentError if !@adj_list.include?(vet1) || !@adj_list.include?(vet2)

        @adj_list[vet1] << vet2
        @adj_list[vet2] << vet1
      end

      ### Delete edge ###
      def remove_edge(vet1, vet2)
        raise ArgumentError if !@adj_list.include?(vet1) || !@adj_list.include?(vet2)

        # Remove edge vet1 - vet2
        @adj_list[vet1].delete(vet2)
        @adj_list[vet2].delete(vet1)
      end

      ### Add vertex ###
      def add_vertex(vet)
        return if @adj_list.include?(vet)

        # Add a new linked list in the adjacency list
        @adj_list[vet] = []
      end

      ### Delete vertex ###
      def remove_vertex(vet)
        raise ArgumentError unless @adj_list.include?(vet)

        # Remove the linked list corresponding to vertex vet in the adjacency list
        @adj_list.delete(vet)
        # Traverse the linked lists of other vertices and remove all edges containing vet
        for vertex in @adj_list
          @adj_list[vertex.first].delete(vet) if @adj_list[vertex.first].include?(vet)
        end
      end

      ### Print adjacency list ###
      def __print__
        puts 'Adjacency list ='
        for vertex in @adj_list
          tmp = @adj_list[vertex.first].map { |v| v.val }
          puts "#{vertex.first.val}: #{tmp},"
        end
      end
    end

## 9.2.3 Efficiency Comparison

Assuming the graph has \(n\) vertices and \(m\) edges, Table 9-2 compares the time efficiency and space efficiency of adjacency matrices and adjacency lists. Note that the adjacency list (linked list) corresponds to the implementation used in this section, while the adjacency list (hash table) refers specifically to the implementation where all linked lists are replaced with hash tables.

Table 9-2 Comparison of adjacency matrix and adjacency list

| Adjacency matrix | Adjacency list (linked list) | Adjacency list (hash table)
--- | --- | --- | ---
Determine adjacency | \(O(1)\) | \(O(n)\) | \(O(1)\)
Add an edge | \(O(1)\) | \(O(1)\) | \(O(1)\)
Remove an edge | \(O(1)\) | \(O(n)\) | \(O(1)\)
Add a vertex | \(O(n)\) | \(O(1)\) | \(O(1)\)
Remove a vertex | \(O(n^2)\) | \(O(n + m)\) | \(O(n)\)
Memory space usage | \(O(n^2)\) | \(O(n + m)\) | \(O(n + m)\)

Observing Table 9-2, it appears that the adjacency list (hash table) has the best time efficiency and space efficiency. However, in practice, operating on edges in the adjacency matrix is more efficient, requiring only a single array access or assignment operation. Overall, adjacency matrices embody the principle of "trading space for time", while adjacency lists embody "trading time for space".

##### Feel free to drop your insights, questions or suggestions