Neocortex 🧠

Search

Search IconIcon to open search

Edge List

Last updated Jan 23, 2022 Edit Source

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]:

MethodRunning 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


Interactive Graph