Graph Representation in Memory: Difference between revisions
| Line 22: | Line 22: | ||
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. | ||
Space requirements: | Space requirements: | ||
Revision as of 21:49, 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. 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:
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.