Hello everyone.
In this note, I decided to list the main data structures used for storing graphs in computer science, as well as discuss a few more structures that have somehow 'crystalized' in my mind.
So, let's get started. But not from the very beginning—I think we all already know what a graph is and what types there are (directed, undirected, weighted, unweighted, with multiple edges and loops or without them).
So, let's go. What options do we have for data structures for 'graph storage'?
1. Matrix Data Structures
1.1 Adjacency Matrix. An adjacency matrix is a matrix where the headings of the rows and columns correspond to the indices of the graph vertices, and the value of each element a(i,j) is determined by the presence or absence of edges between vertices i and j (clearly, for an undirected graph, this matrix will be symmetric, or one can agree that we store values only above the main diagonal). For unweighted graphs, a(i,j) can be specified as the number of edges from i to j (if there is no such edge, then a(i,j)= 0), and for weighted graphs, it is also specified as the weight (total weight) of the mentioned edges.
1.2 Incidence Matrix. In this case, our graph is also stored in a table, where the row indices typically correspond to the numbers of its vertices, and the column indices correspond to pre-numbered edges. If a vertex and an edge are incident to each other, a non-zero value is recorded in the corresponding cell (for undirected graphs, 1 is recorded for the incidence of the vertex and edge; for directed graphs, '1' if the edge 'exits' from the vertex and '-1' if it 'enters' it (it's quite easy to remember, as the minus sign also 'enters' the number '-1')). For weighted graphs, instead of 1 and -1, the total weight of the edge can again be specified.
2. Enumerative Data Structures
2.1 Adjacency List. Well, everything here seems simple. Each vertex of the graph can generally be associated with any enumerative structure (list, vector, array, etc.) that will store the numbers of all vertices adjacent to it. For directed graphs, we will only include those adjacent vertices that have a directed edge from the reference vertex. For weighted graphs, the implementation will be more complex.
2.2 Edge List. A fairly popular data structure. The edge list, as Captain Obvious hints, represents the actual list of the graph's edges, each defined by a starting vertex, an ending vertex (for undirected graphs, the order does not matter, although to unify, various rules can be applied, such as specifying vertices in ascending order), and a weight (only for weighted graphs).
You can find more detailed information about the above-mentioned list-matrices (with illustrations) at, for example, .
2.3 Adjacency Array. Not the most commonly used structure. Essentially, it represents a form of 'packing' adjacency lists into a single enumerative structure (array, vector). The first n (corresponding to the number of vertices in the graph) elements of this array contain the starting indices of this same array, from which all vertices adjacent to the corresponding vertex are listed sequentially.
Here, I found the most understandable (for myself) explanation:
3. Adjacency Vector and Associative Adjacency Array
It so happened that the author of these lines, not being a professional programmer but having periodically dealt with graphs, most often worked with edge lists. Indeed, it is convenient when there are multiple loops and edges in the graph. Thus, in the evolution of classical edge lists, I propose to pay attention to their 'development/branching/modification/mutation', namely: adjacency vector and associative adjacency array.
3.1 Adjacency Vector
Case (a1): Unweighted Graph
We will call the adjacency vector for an unweighted graph an ordered set of an even number of integers (a[2i], a[2i+1], ..., where i is numbered starting from 0), in which each pair of numbers a[2i], a[2i+1] defines an edge of the graph between vertices a[2i] and a[2i+1], respectively.
This format of representation does not indicate whether the graph is directed (both options are possible). When using the format for a graph, it is assumed that the edge is directed from a[2i] to a[2i+1]. Hereinafter: for undirected graphs, the requirements for the order of vertex notation may apply if necessary (for example, to list the vertex with the smaller assigned number first).
In C++, the adjacency vector is effectively defined using std::vector, hence the name of this data structure.
Case (a2): unweighted graph, edge weights are integers.
Similarly to case (a1), we will define the adjacency vector for a weighted graph with integer edge weights as an ordered set (dynamic array) of numbers (a[3i], a[3i+1], a[3i+2],…, where i starts from 0), where each 'triplet' of numbers a[3i], a[3i+1], a[3i+2] denotes an edge of the graph between the vertices numbered a[3i] and a[3i+1] respectively, and the value a[3i+2] is the weight of this edge. Such a graph can also be directed or undirected.
Case (b): unweighted graph, edge weights are non-integer.
Given that heterogeneous elements cannot be stored in a single array (vector), the following implementation is possible. The graph is stored in a pair of vectors, where the first vector is the adjacency vector of the graph without specifying weights, and the second vector contains the corresponding weights (possible implementation for C++: std::pair). Thus, for an edge defined by the pair of vertices at indices 2i, 2i+1 of the first vector, the weight will equal the element at index i of the second vector.
But why is this necessary?
Well, for the author of these lines, it seemed quite useful for solving a number of tasks. From a formal standpoint, there will be such advantages:
- The adjacency vector, like any other 'enumeration' structure, is quite compact, takes up less memory than the adjacency matrix (for sparse graphs), and is relatively simple to implement.
- Graph vertices can essentially be labeled with negative numbers. It might come in handy for some 'twist'.
- Graphs may contain multiple edges and multiple loops, and they can have different weights (positive, negative, even zero). There are no restrictions here.
- Edges can also be assigned different properties – see section 4 for more.
However, it must be acknowledged that this 'list' does not imply quick access to the edge. Here, the Adjacency Associative Array comes to the rescue, as discussed below.
3.2 Adjacency Associative Array
So, if we need access to a specific edge, its weight, and other properties, and memory constraints prevent the use of an adjacency matrix, let’s consider how we could modify the adjacency vector to solve this problem. Thus, the key is the edge of the graph, which can be defined as an ordered pair of integers. What does this resemble? Isn’t it like a key in an associative array? If so, why not implement it? Let’s create an associative array where each key—an ordered pair of integers—will correspond to a value—an integer or real number that specifies the weight of the edge. In C++, it makes sense to implement this structure using the std::map container (std::map<std::pair, int> or std::map<std::pair, double>), or std::multimap if multiple edges are anticipated. And here we have a structure for storing graphs that takes up less memory than 'matrix' structures, can define graphs with multiple loops and edges, and even has no strict requirements for non-negativity of vertex numbers (not sure who needs this, but still).
4. Data structures can be tedious, but something is missing
Indeed, when solving certain problems, we may need to assign certain characteristics to the edges of the graph and, correspondingly, store them. If it is possible to unambiguously reduce these characteristics to integers, then it is feasible to store such 'graphs with additional characteristics' using extended versions of the adjacency vector and adjacency associative array.
Let’s say we have an unweighted graph, where each edge needs to store, for example, 2 additional attributes defined by integers. In this case, we can define its adjacency vector as an ordered set of not "pairs" but "quatuors" of integers (a[2i], a[2i+1], a[2i+2], a[2i+3]…), where a[2i+2] and a[2i+3] will determine the attributes of the corresponding edge. For a graph with integer weights, the order is generally similar (the only difference being that the attributes will follow the edge weight and be described by elements a[2i+3] and a[2i+4], and the edge will be defined not by 4, but by 5 ordered numbers). For a graph with non-integer weights, the attributes can be recorded in its unweighted component.
When using an associative array for adjacency in graphs with integer edge weights, it's possible to define a value not as a single number, but as an array (vector) of numbers that specify, in addition to the edge weight, all its other necessary attributes. In this case, the inconvenience for the situation with non-integer weights is the need to define the attribute as a floating-point number (yes, this is inconvenient, but if there are not too many such attributes, and if they are not defined as too "clever" doubles, then it may be manageable). Therefore, in C++, extended associative arrays for adjacency can be defined as follows: std::map<std::pair, std::vector> or std::map<std::pair, std::vector>, where the first value in the "value-vector-by-key" will be the edge weight, followed by the numeric designations of its attributes.
Literature:
On graphs and algorithms in general:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algorithms: Building and Analysis, 2nd Edition: Translated from English – Moscow: Williams Publishing House, 2011.
2. Harari, Frank. Graph Theory. Moscow: Mir, 1973.
The author's report on these very vector and associative array for adjacency:
3. S.A. Chernouhov. Adjacency vector and adjacency map as data structures to represent a graph // Collection of articles from the International Scientific and Practical Conference "Problems of Implementing the Results of Innovative Developments and Their Solutions" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, pp. 65-69
Useful internet resources on the topic:
4.
5.
Source: habr.com
