Adjacency Matrix Graph Representation

How Adjacency Matrix Works

An Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. For undirected graphs, the matrix is symmetric.

Pros:

• Representation is easier to implement and follow
• Removing an edge takes O(1) time
• Queries like whether there is an edge from vertex 'u' to vertex 'v' are efficient and can be done O(1)

Cons:

• Consumes more space O(V^2)
• Even if the graph is sparse(contains less number of edges), it consumes the same space
• Adding a vertex is O(V^2) time

class Graph:
    matrix
    vertices

    function addVertex():
        newVertex = new array of size vertices filled with 0
        for each row in matrix:
            row.append(0)
        matrix.append(newVertex)
        vertices++
        visualize()

    function removeVertex(v):
        if v < 0 or v >= vertices:
            return
        matrix.removeAt(v)
        for each row in matrix:
            row.removeAt(v)
        vertices--
        visualize()

    function addEdge(v1, v2):
        if v1 < 0 or v1 >= vertices or v2 < 0 or v2 >= vertices:
            return
        matrix[v1][v2] = 1
        matrix[v2][v1] = 1  // for undirected graph
        visualize()

    function removeEdge(v1, v2):
        if v1 < 0 or v1 >= vertices or v2 < 0 or v2 >= vertices:
            return
        matrix[v1][v2] = 0
        matrix[v2][v1] = 0  // for undirected graph
        visualize()

    function getNeighbors(v):
        if v < 0 or v >= vertices:
            return []
        neighbors = []
        for i from 0 to vertices - 1:
            if matrix[v][i] == 1:
                neighbors.append(i)
        return neighbors