# Representing Graphs #### Adjacency Matrix Pros: * Space efficient for representing dense graphs * Edge weight lookup is $O(1)$ * Simplest graph representation Cons: * Requires $O(V^2)$ space (graphs with more than 10,000 nodes become infeasible quickly) * Iterating over all edges takes $O(V^2)$ time  #### Adjacency List An **adjacency list** is a way to represent a graph as a map from nodes to lists of edges. Pros * Space efficient for sparse graphs * Efficient for iterating over all edges Cons: * less space efficient on dense graphs * Edge weight lookup is $O(E)$ (this rarely happens though) * Slightly more complex graph representation  #### Edge List Pros: * Space efficient for representing sparse graphs * Iterating over all edges is efficient * Very simply structure Cons: * Less space efficient for denser graphs * Edge weight lookup is $O(E)$  --- Backlinks: [Graph-Theory](Graph-Theory.md)