Adjacency Matrix for Undirected Graphs

Space: O(n²)Edge Query: O(1)Symmetric Matrix

📊Understanding Undirected Graph Adjacency Matrices

An adjacency matrix for an undirected graph is a square matrix used to represent connections between vertices. For a graph with n vertices, the adjacency matrix is an n×n symmetric matrix where each cell [i][j] indicates whether there is an edge between vertex i and vertex j.

In an undirected graph, the matrix is always symmetric because if there's an edge from vertex A to vertex B, there's also an edge from B to A.

matrix[i][j] = matrix[j][i] = 1 if edge exists between vertices i and j, 0 otherwise

💻Implementation

// Adjacency Matrix for Undirected Graph
class UndirectedGraph {
  constructor(numVertices) {
    this.numVertices = numVertices;
    this.adjMatrix = Array(numVertices).fill(null)
      .map(() => Array(numVertices).fill(0));
  }
  
  // Add an edge between two vertices (symmetric)
  addEdge(vertex1, vertex2) {
    if (vertex1 >= 0 && vertex1 < this.numVertices && 
        vertex2 >= 0 && vertex2 < this.numVertices) {
      this.adjMatrix[vertex1][vertex2] = 1;
      this.adjMatrix[vertex2][vertex1] = 1; // Symmetric for undirected
    }
  }
  
  // Remove an edge between two vertices (symmetric)
  removeEdge(vertex1, vertex2) {
    if (vertex1 >= 0 && vertex1 < this.numVertices && 
        vertex2 >= 0 && vertex2 < this.numVertices) {
      this.adjMatrix[vertex1][vertex2] = 0;
      this.adjMatrix[vertex2][vertex1] = 0; // Symmetric for undirected
    }
  }
  
  // Check if edge exists between two vertices
  hasEdge(vertex1, vertex2) {
    if (vertex1 >= 0 && vertex1 < this.numVertices && 
        vertex2 >= 0 && vertex2 < this.numVertices) {
      return this.adjMatrix[vertex1][vertex2] === 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;
  }
  
  // Get degree of a vertex (number of edges)
  getDegree(vertex) {
    return this.getNeighbors(vertex).length;
  }
  
  // Create from edge list
  static fromEdgeList(numVertices, edges) {
    let graph = new UndirectedGraph(numVertices);
    edges.forEach(([vertex1, vertex2]) => {
      graph.addEdge(vertex1, vertex2);
    });
    return graph;
  }
  
  // Display matrix
  printMatrix() {
    console.log("Adjacency Matrix (Undirected):");
    for (let i = 0; i < this.numVertices; i++) {
      console.log(this.adjMatrix[i].join(" "));
    }
  }
}

// Example usage
let graph = new UndirectedGraph(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) - updates 2 cells
• Remove edge: O(1) - updates 2 cells
• Get neighbors: O(n)

Space & Properties

• Space: O(n²) always
• Symmetry: Matrix is always symmetric
• Diagonal: Usually 0 (no self-loops)
• Memory efficiency: Can store only upper triangle

✅ Best Use Cases

• Social networks: Friendship connections
• Road networks: Bidirectional roads
• Communication networks: Two-way connections
• Dense graphs: When most vertices are connected
• Matrix operations: Graph algorithms using linear algebra

🔄 Key Differences

• Symmetric matrix: matrix[i][j] = matrix[j][i]
• Degree concept: Number of neighbors for each vertex
• Memory optimization: Can store only upper/lower triangle
• Edge counting: Each edge counted once, not twice
• No direction: Relationships are bidirectional