Graph Representation in Memory: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
No edit summary
Line 5: Line 5:


<font color=darkgray>TODO [[CLRS]] page 589, [[DDIA]] location 1392.</font>
<font color=darkgray>TODO [[CLRS]] page 589, [[DDIA]] location 1392.</font>
=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=
=Adjacency Lists=

Revision as of 21:32, 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.

Cases when adjacency matrix representation is preferred:

  • dense graphs.
  • When we need to tell quickly if there is an edge connecting two given vertices.

Continue CLRS page 590.