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
- sparse graph — A graph with far fewer edges than the maximum possible, closer to V than to V squared.
- adjacency matrix — A graph representation as a V-by-V grid in which the cell at row i, column j records whether, or with what weight, an edge runs from vertex i to vertex j.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers