Graph Representation in Memory: Difference between revisions
Jump to navigation
Jump to search
| Line 21: | Line 21: | ||
=Adjacency Matrices= | =Adjacency Matrices= | ||
Applies to directed and undirected graphs. | Applies to directed and undirected graphs. | ||
Space requirements: | |||
Operations supported: | |||
Cases when adjacency matrix representation is preferred: | Cases when adjacency matrix representation is preferred: | ||
| Line 26: | Line 32: | ||
* When we need to tell quickly if there is an edge connecting two given vertices. | * When we need to tell quickly if there is an edge connecting two given vertices. | ||
<font color= | <font color=darkkhaki>[[CLRS]] page 590.</font> | ||
Revision as of 21:43, 28 September 2021
Internal
Overview
TODO CLRS page 589, DDIA location 1392.
Graph Input Size
When it comes to graphs, the input size is given by two parameters: the number of vertices (n) and the number of edges (m).
For a connected, undirected graph with n vertices, the number of edges ranges from n - 1 and n (n - 1)/2.
Adjacency Lists
Applies to directed and undirected graphs.
An adjacency list representation provides a memory-efficient way of representing sparse graphs, so it is usually the method of choice.
Continue CLRS page 590.
Adjacency Matrices
Applies to directed and undirected graphs.
Space requirements:
Operations supported:
Cases when adjacency matrix representation is preferred:
- dense graphs.
- When we need to tell quickly if there is an edge connecting two given vertices.
CLRS page 590.