Graph Representation in Memory: Difference between revisions
Jump to navigation
Jump to search
(Created page with "=Internal= * Graphs <font color=darkgray>TODO CLRS page 589, DDIA location 1392.</font> ==Adjacency Lists== Applies...") |
No edit summary |
||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Graph#Representing_Graphs_in_Computer_Memory|Graphs]] | * [[Graph#Representing_Graphs_in_Computer_Memory|Graphs]] | ||
=Overview= | |||
<font color=darkgray>TODO [[CLRS]] page 589, [[DDIA]] location 1392.</font> | <font color=darkgray>TODO [[CLRS]] page 589, [[DDIA]] location 1392.</font> | ||
=Adjacency Lists= | |||
Applies to directed and undirected graphs. | Applies to directed and undirected graphs. | ||
| Line 12: | Line 14: | ||
<font color=darkgray>Continue [[CLRS]] page 590.</font> | <font color=darkgray>Continue [[CLRS]] page 590.</font> | ||
=Adjacency Matrices= | |||
Applies to directed and undirected graphs. | Applies to directed and undirected graphs. | ||
Revision as of 21:24, 28 September 2021
Internal
Overview
TODO CLRS page 589, DDIA location 1392.
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.