Algorithms and Data Structures - Graphs Representation

Adjacency Matrix

Asymptotic Complexity

• Time complexity:
  • Insertion: O(1)
  • Deletion: O(1)
• Space complexity: O(V^2)

Pros

• Simple to implement
• Fast to access edge (u, v), O(1), fast to add and remove edges

Cons

• Space complexity is O(V^2)
• Its not efficient for sparse graphs

Demos

• Adjacency Matrix
• Undirected Graph
• Directed Graph
• Adjacency Matrix - Playground
• Adjacency Matrix - Weighted

Adjacency List

Asymptotic Complexity

• Time complexity:
  • Insertion: O(V) using list, O(1) using Hash Table
  • Deletion: O(V) using list, O(1) using Hash Table
• Space complexity: O(V + E)

Pros

• Space complexity is O(V + E)
• Efficient for sparse graphs

Cons

• Slow to access edge (u, v), O(V) using list, but can be O(1) using Hash Table

Demos

• Adjacency List
• Adjacency List - With Hash Table
• Adjacency List - Playground

Edge List

Asymptotic Complexity

• Time complexity:
  • Insertion: O(1)
  • Deletion: O(E)
• Space complexity: O(E)

Pros

• Space complexity is O(E)
• Fast to add edges

Cons

• Slow to access edge (u, v), O(E)

Demos

• Edge List

References

• Other Algorithms & Data Structures