dense graph

A graph in which most pairs of vertices are connected, so the edge count is close to V squared.

In more detail

For dense graphs an adjacency matrix wastes little space and gives O(1) edge checks. Algorithms whose cost depends on E, such as Kruskal's, slow down on them.

Related terms

Taught in

References