Edge List
The edge list structure basically holds a list of all the edges in a graph as well as a list of all the vertices. It is a simple yet effective way to store a graph. Since we store vertices and edges, it takes $O(n+m)$ space.^[1]:
| Method | Running Time |
|---|---|
| numVertices(), numEdges() | $O(1)$ |
| vertices() | $O(n)$ |
| edges() | $O(m)$ |
| getEdge(u,v), outDegree(v), inDegree(v) | $O(m)$ |
| insertVertex(x), insertEdge(u, v, x), removeEdge(e) | $O(1)$ |
| removeVertex(v) | $O(m)$ |
[1]: n is the number of vertices, m is the number of edges