Graph Representation in Memory: Difference between revisions
No edit summary |
|||
| Line 20: | Line 20: | ||
=Adjacency Matrices= | =Adjacency Matrices= | ||
<font color=darkkhaki>[[CLRS]] page 590.</font> | <font color=darkkhaki>[[CLRS]] page 590.</font> | ||
The edges of a graph are represented using a matrix. | The edges of a graph are represented using a matrix. | ||
Applies to directed and undirected graphs. The matrix is denoted by A, and it is a nxn square matrix, where n is the number of vertices in the graph. The semantics is A<sub>ij</sub>=1 if and only if there's an edge between vertices i and j in the graph. It can be extended for [[Graph#Parallel_Arcs|parallel arcs]] and [[Graph#Weighted_Graphs|weighted graphs]]. For parallel arcs, A<sub>ij</sub> denotes the number of edges. For weighted graphs, A<sub>ij</sub> denotes the weight of the edge. For directed graphs, if the arc is directed from i to j, A<sub>ij</sub>=+1 and if it is directed from j to i, A<sub>ij</sub>=-1. | Applies to directed and undirected graphs. The matrix is denoted by A, and it is a nxn square matrix, where n is the number of vertices in the graph. The semantics is A<sub>ij</sub>=1 if and only if there's an edge between vertices i and j in the graph. It can be extended for [[Graph#Parallel_Arcs|parallel arcs]] and [[Graph#Weighted_Graphs|weighted graphs]]. For parallel arcs, A<sub>ij</sub> denotes the number of edges. For weighted graphs, A<sub>ij</sub> denotes the weight of the edge. For directed graphs, if the arc is directed from i to j, A<sub>ij</sub>=+1 and if it is directed from j to i, A<sub>ij</sub>=-1. | ||
Revision as of 22:03, 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
CLRS page 590.
A data structure that keeps track of vertices and edges as independent entities. Applies to directed and undirected graphs. It has an array (or a list) of vertices and an array (or a list) of edges. These two arrays cross-reference each other. Each edge has two pointers, one for each of its endpoints. For directed graphs we keep track of which one is the head and which one is the tail. Each vertex points to all of the edges of which it is a member. For directed graphs, a vertex keeps track of each of the edges it is the tail.
The space requirements for this data structure is Θ(n + m). An adjacency list representation provides a memory-efficient way of representing sparse graphs, so it is usually the method of choice. Adjacency lists are very well suited for graph search.
Adjacency Matrices
CLRS page 590.
The edges of a graph are represented using a matrix. Applies to directed and undirected graphs. The matrix is denoted by A, and it is a nxn square matrix, where n is the number of vertices in the graph. The semantics is Aij=1 if and only if there's an edge between vertices i and j in the graph. It can be extended for parallel arcs and weighted graphs. For parallel arcs, Aij denotes the number of edges. For weighted graphs, Aij denotes the weight of the edge. For directed graphs, if the arc is directed from i to j, Aij=+1 and if it is directed from j to i, Aij=-1.
Space requirements: an adjacency matrix requires space quadratic in the number of vertices Θ(n2). For dense graphs this is fine but for sparse graphs, it is wasteful.
Cases when adjacency matrix representation is preferred:
- dense graphs.
- When we need to tell quickly if there is an edge connecting two given vertices.