Graph Representation in Memory: Difference between revisions
Jump to navigation
Jump to search
| Line 20: | Line 20: | ||
=Adjacency Matrices= | =Adjacency Matrices= | ||
Applies to directed and undirected graphs. | The edges of a graph are represented using a matrix. | ||
Applies to directed and undirected graphs. It can be extended for [[Graph#Parallel_Arcs|parallel arcs]] and [[Graph#Weighted_Graphs|weighted graphs]]. | |||
Revision as of 21:45, 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
The edges of a graph are represented using a matrix. Applies to directed and undirected graphs. It can be extended for parallel arcs and weighted 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.