Efficient Graph Design: Matrix vs List Decision Guide | Data Structure

let's say we have a graph:

How do we represent this Graph in data structure?

Adjacency List:

Represent this graph as an

array [ ]

1. This array is going to have the equal number of values as there are nodes of the graph.
2. Every index that you see inside of this array points to the correesponding node that has same number identifier.
3. The numerical value of any node that is connected to the corresponding node

Each node , we take is as the index of an Array:

[
0th index to represent 0th node,
1st index to represent 1st index,
2nd index to represent 2nd index,
.... each index in the array represents that node
]

Each values in the array represents the nodes. that the index node connects to:

[
[1, 3],   here index 0(node) connects to 1 & 3
[0].  ,   here index 1(node) connects to 0
[3, 8],   here index 2(node) connects to node 3 & 8
[0, 2, 4, 5] , index 3(node) connects to 0, 2, 4, & 5 nodes
]

A complete adjacencyList to represent our original graph looks like:

const adjacencyList = [
  [1, 3],  // 0 connects to 1,3
  [0],    // 1 connects to 0
  [3, 8],  // 2 connects to 3,8
  [0, 2, 4, 5], // 3 connects to 0,2,4,5
  [3, 6],  // 4 connects to 3,6
  [3],    // 5 connects to 3
  [4, 7],  // 6 connects to 4,7
  [6],    // 7 connects to 6
  [2]    // 8 connects to 2
];

For Graphs With String:

Is there every going to be a chance where identifier for these vertex nodes are going to be a string?

Yes: for example:

If this is the case then, adjacency list is going to take the form of object where:

1. Key is going to be every single node
2. Values is array containing these connected nodes as String

{
    A: ['X'],
    B: ['X'],
    C: ['Y'],
    D: ['X'],
    X: ['A' , 'B', 'D', 'Y']
    Y: ['X', 'C']
}

If we were to look up for value of B, then we can easily do so Graph['B']

This is the main benefit of using adjacency list. We get really fast lookup & it's easy to traverse from one node to it's children or to it's siblings.

Adjacency Matrix:

It uses 2D array or matrix, here we are going to represent each node as outsides arrays' indices.

similar to adjacency list

[
 0 :
 1 :
 2 :
 3 :
 4 :
 5 :
]

And for every array in the index, (index representing a node) we will represent the connection / edges in the Graph.

0 for no connections

1 for connections from outside index to inside index node as a value

     0  1  2  3  4  5  
 0 : [                ]   
 1 : [                ]       
 2 : [                ]   
 3 : [                ]   
 4 : [                ]   
 5 : [                ]   
]

For the index 0, outside we represent it as a node, and check the graph, where node 0 is connected to what other nodes?

1. is Node 0 connected to node 0?
2. is node 0 connected to node 1?
3. is node 0 connected to node 2?
4. is node 0 connected to node 3?
5. is node 0 connected to node 4?
6. is node 0 connected to node 5?

      0. 1. 2. 3. 4. 5
 0 : [0. 1  0. 1. 0. 0. ]   
 1 : [                  ]
 2 : [                  ]   
 3 : [                  ]   
 4 : [                  ]    
 5 : [                  ]   
] 

If we complete this matrix this is how it looks:

[     0  1  2  3  4  5  
 0 : [1. 1  0. 1. 0. 0. ]   
 1 : [1. 1. 0. 1  0. 0  ]       
 2 : [0. 0  1  1  0  0  ]   
 3 : [1. 1. 1. 1  1. 0  ]   
 4 : [0  0. 0. 1. 1. 1  ]   
 5 : [0  0. 0. 0  1. 1  ]   
]

This is a adjacency matrix. It's a dense data structure.

It takes up a lot of space.

Space complexity is going to be number of nodes squared because that's how many units that we have to store inside our 2D array.

Whereas Adjacency list is depended on the number of edges that are in the graph. Most of the time ends up being smaller, but once again depends on the graph so we need to evaluate before we determine on which Adjacency relationship list or matrix to use?

Space complexity:

1. Adjacency Matrix: O(V²) - Always requires V×V space regardless of edges
2. Adjacency List: O(V+E) - Space scales with actual edges present

1. Choose matrix when:
2. Graph is dense (E ≈ V²)
3. Need fast edge lookups O(1)
4. Graph is small
5. Choose list when:
6. Graph is sparse (E << V²)
7. Memory is constrained
8. Need fast vertex traversal

Time Complexity:

• Adjacency Matrix:
• Edge lookup: O(1)
• Add/remove edge: O(1)
• Add vertex: O(V²)
• Find neighbors: O(V)

• Adjacency List:
• Edge lookup: O(E)
• Add edge: O(1)
• Add vertex: O(1)
• Find neighbors: O(degree(v))

Real-world use cases:

• Matrix: Social networks, dense routing networks
• List: Web graphs, road networks, sparse systems

Practical considerations:

• Matrix benefits: Simple implementation, direct indexing
• List benefits: Better for most real-world graphs (naturally sparse), easier to modify

Implementation variations:

• Can use hash tables instead of arrays for faster lookups
• Weighted edges can store weights instead of binary values
• Directed vs undirected affects storage pattern

#graph #dataStructures #adjacencyList #adjacencyMatrix