DEV Community

Akashdeep
Akashdeep

Posted on

1

Big O Complexity for Graphs: Adjacency Matrix vs Adjacency List

Graphs can be represented in two main ways: Adjacency Matrix and Adjacency List. Each method has its own pros and cons depending on how much memory it needs and how quickly it can handle different operations.

1. Space Complexity

Adjacency Matrix : O(V^2)
Adjacency List : O(V+E)

  • V: Number of vertices.
  • E: Number of edges.
  • Adjacency Matrix requires a VƗV grid, making it less efficient for sparse graphs.
  • Adjacency List only stores edges for each vertex, making it space-efficient for sparse graphs.

2. Time Complexity: Adding a Vertex

Adjacency Matrix : O(V^2)
Adjacency List : O(1)

  • Adjacency Matrix: Adding a vertex may require creating a new š‘‰+1Ɨš‘‰+1 matrix and copying the old matrix, which is expensive.
  • Adjacency List: Simply add a new empty list for the new vertex, which is constant time.

3. Time Complexity: Adding an Edge

Adjacency Matrix : O(1)
Adjacency List : O(1)

Both representations allow constant-time edge additions:

  • Matrix: Set the matrix cell to 1 (or edge weight).
  • List: Append the edge to the list.

4. Time Complexity: Removing an Edge

Adjacency Matrix : O(1)
Adjacency List : O(E/V)

  • Adjacency Matrix: Directly unset the cell, which is constant time.
  • Adjacency List: Requires searching through the list for the edge, leading to O(E/V) time on average.

5. Time Complexity: Removing a Vertex

Adjacency Matrix : O(V^2)
Adjacency List : O(V+E)

  • Adjacency Matrix: Removing a vertex involves deleting its row and column, which can require shifting elements in the matrix.
  • Adjacency List: Removing a vertex requires deleting the list for the vertex and traversing all other lists to remove edges to the vertex.

Choosing the Right Representation

  • Adjacency Matrix:
    Suitable for dense graphs where Eā‰ˆV2.
    Offers constant-time edge operations but consumes more space.

  • Adjacency List:
    Ideal for sparse graphs where Eā‰ŖV2.
    Space-efficient and generally faster for operations involving vertices.

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (1)

Collapse
 
akshay_sabu_061f86c4b261e profile image
Akshay Sabu ā€¢

informative

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

šŸ‘‹ Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay