Adjacency Matrix for Directed Graphs

Space: O(n²)Edge Query: O(1)Matrix-based

📊Understanding Adjacency Matrices

An adjacency matrix is a square matrix used to represent a directed graph. For a graph with n vertices, the adjacency matrix is an n×n matrixwhere each cell [i][j] indicates whether there is an edge from vertex i to vertex j.

In a directed graph, the matrix is typically not symmetricbecause an edge from vertex A to vertex B doesn't necessarily mean there's an edge from B to A.

matrix[i][j] = 1 if edge exists from vertex i to vertex j, 0 otherwise

💻Implementation

// Adjacency Matrix for Directed Graph
class DirectedGraph {
  constructor(numVertices) {
    this.numVertices = numVertices;
    this.adjMatrix = Array(numVertices).fill(null)
      .map(() => Array(numVertices).fill(0));
  }
  
  // Add an edge from source to destination
  addEdge(src, dest) {
    if (src >= 0 && src < this.numVertices && 
        dest >= 0 && dest < this.numVertices) {
      this.adjMatrix[src][dest] = 1;
    }
  }
  
  // Remove an edge from source to destination
  removeEdge(src, dest) {
    if (src >= 0 && src < this.numVertices && 
        dest >= 0 && dest < this.numVertices) {
      this.adjMatrix[src][dest] = 0;
    }
  }
  
  // Check if edge exists
  hasEdge(src, dest) {
    if (src >= 0 && src < this.numVertices && 
        dest >= 0 && dest < this.numVertices) {
      return this.adjMatrix[src][dest] === 1;
    }
    return false;
  }
  
  // Get all neighbors of a vertex
  getNeighbors(vertex) {
    let neighbors = [];
    for (let i = 0; i < this.numVertices; i++) {
      if (this.adjMatrix[vertex][i] === 1) {
        neighbors.push(i);
      }
    }
    return neighbors;
  }
  
  // Create from edge list
  static fromEdgeList(numVertices, edges) {
    let graph = new DirectedGraph(numVertices);
    edges.forEach(([src, dest]) => {
      graph.addEdge(src, dest);
    });
    return graph;
  }
  
  // Display matrix
  printMatrix() {
    console.log("Adjacency Matrix:");
    for (let i = 0; i < this.numVertices; i++) {
      console.log(this.adjMatrix[i].join(" "));
    }
  }
}

// Example usage
let graph = new DirectedGraph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.printMatrix();

🔍Properties & Complexity

Time Complexity

• Edge lookup: O(1)
• Add edge: O(1)
• Remove edge: O(1)
• Get neighbors: O(n)

Space & Properties

• Space: O(n²) always
• Memory: Fixed regardless of edge count
• Representation: Dense storage
• Matrix ops: Easy to perform

✅ Best Use Cases

• Dense graphs: Many edges relative to vertices
• Fast edge queries: Frequent "is there an edge?" checks
• Matrix operations: Graph algorithms using linear algebra
• Small graphs: When n² space is acceptable
• Complete graphs: Nearly all possible edges exist

⚠️ Limitations

• Space inefficient: Wastes memory for sparse graphs
• Fixed size: Difficult to add/remove vertices
• Large graphs: O(n²) space becomes prohibitive
• Iteration: O(n) to find all neighbors
• Cache performance: Poor for very large matrices