Adjacency matrix graph data structure

Disambiguation

We refer to the ‘modern’ adjacency matrix where adjacent vertices have a reference to their edge object in their corresponding cell and otherwise hold null

• The other option is for the matrix to be True/False values

Where $n$ is the # of vertices, $m$ is the # of edges

Operation	Complexity	Notes
Space	$O(n^2)$	2D matrix, indices 0 to n-1
insertVertex(x)	$O(n^2)$	Even with a Dynamic array, worst case we have to copy/realloc entire matrix when full. Average can be O(2n) though
insertEdge(u,v,x)	$O(1)$	Add 2 pointers to the relevant indexes
removeVertex(v)	$O(n^2)$	Copy and reallocate - we might remove a vertex in the middle row/col, unavoidable worst-case
removeEdge(e)	$O(1)$	Go to the [u][v] and [v][u] (edge obj storing vertex info)
degree(v)	$O(1)$	O(n) usually but we could keep a counter for each vertex
incidentEdges(v)	$O(n)$	Traverse corresponding vertex row/column
getEdge(u,v)	$O(1)$	Go to [u][v]
endVerticesOf(e)	$O(1)$	Return the stored values (assume edge obj stores)
opposite(v,e)	$O(1)$	Return other stored value
vertices()	$O(n)$	Traverse axis
edges()	$O(n^2)$	Traverse all indices1
numVertices()	$O(1)$	Dependent on a counter variable
numEdges()	$O(1)$	Dependent on a counter variable

Directed graph information

See this link

Footnotes

1. Unsure, linked document says O(m) ↩