Edge List

Implementation

• Represent as a table (array of objects) that stores every edge along with it’s associated weight
• Space: $O(E)$

Operations

• Connectedness
  • Is A connected to B?
  • Do a linear scan for (A, B)
  • $O(E)$ time complexity
• Adjacency
  • What are A’s adjacent nodes?
  • Do a linear scan for A on the left
  • $O(E)$ time complexity

$O(E)$ is problematic because in a dense graph $O(|E|)\sim O(|V|{)}^2$