“This is the 27th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

7.3.2 adjacency table

In order to solve the graph with fewer edges than vertices, the structure of adjacency matrix will waste a lot of space

As follows:

Remember when we talked about storage structures in trees, we talked about a child representation, where you put nodes in an array, and you chain the children of nodes, no matter how many children there are, you don’t waste space. The same idea applies to graph storage. We call this combination of arrays and linked lists a Adjacency List.

Adjacency list processing method:

1. The vertices in the figure are stored in a one-dimensional array. Of course, vertices can also be stored in a singly linked list, but arrays make it easier to read vertices. In addition, for the vertex array, each data element also needs to store a pointer to the first adjacent point, so that it is easy to find the edge information of the vertex.

2. A linear list is constructed for all adjacency points of each vertex Vi in the graph. Since the number of adjacency points is variable, a single linked list is used to store the list.

In the figure above, V1 vertex is adjacent to V0 and V2, so in the edge table of V1, Adjvex is 0 of V0 and 2 of V2 respectively

What is an edge list

Each node of the vertex table is represented by data and Firstedge fields. Data is the data field, which stores the information of vertices, and Firstedge is the pointer field, which points to the first node of the edge table (because it is an undirected graph, so it is called edge table), that is, the first adjacency of this vertex. The side table node consists of adjvex and next fields. Adjvex is an adjacency field that stores the subscript of the adjacency of a vertex in the vertex table, and next stores a pointer to the next node in the edge table.

In directed graphs, the structure of adjacency lists is similar

We can build an inverse adjacency list of digraphs, that is, for each vertex Vi we build a list of links with v as an arc head

It is easy to calculate the degree of entry or exit of a vertex, and it is also easy to determine whether two vertices have arcs.

For weighted network graph, you can add a weight data field in the definition of edge table node to store the weight information

7.3.3 Cross linked list

So for digraphs, adjacency lists are defective. Concern about the degree of the problem, to understand the degree of entry must be traversed the whole graph to know, on the contrary, the inverse adjacency list solved the degree of entry but do not understand the degree of the situation. Is it possible to combine adjacency lists with inverse adjacency lists? The answer is yes, to integrate them. This is the Orthogonal List, a method of storing digrams that we will now talk about.

Redefine the node table node structure

data firstin firstout

Firstin refers to the first node in the entry table of this vertex, and firstout refers to the first node in the exit table of this vertex.

Redefine the edge table node structure

Tailvex refers to the subscript of the starting point of the arc in the vertex table, headvex refers to the subscript of the end point of the arc in the vertex table, headlink refers to the edge table pointer field, pointing to the next edge with the same end point, tallink refers to the edge table pointer field, pointing to the next edge with the same starting point. In the case of a network, you can also add a weight field to store weights.

Examples are as follows:

In the case of vertex V0, firstOut points to V3, the first node in the exit table, so tailvex and headvex are 03, so why are headlink and Taillink empty, because there are no nodes with the same end point as V0? Taillink is empty because there is no node that starts from V0.

There are also some examples in the diagram that you can understand a little bit more

Comrades must have a good look and understand this map!!

The nice thing about a cross linked list is that because it combines the adjacency list with the inverse adjacency list, it’s easy to find arcs that end with Vi, and it’s easy to find arcs that start with Vi, and it’s easier to figure out the degrees of the vertex and the degrees of the vertex

The disadvantage is that the structure is a bit complicated. In the application of digraph, the cross – linked list is a very good data structure model

7.3.4 Adjacency multiple list

The storage structure of digraph is optimized by cross – linked list

In the application of undirected tables, where the focus is on vertices, adjacency lists are a good choice

If you focus on edge manipulation, you need a simpler approach

Redefine the edge table node structure

Where ivex and jvex are the subscripts of two vertices attached to an edge in the vertex table.

Ilink points to the next edge of the attached vertex ivex

Jlink points to the next edge of the attached vertex, jvex

The figure below tells us that it has four vertices and five edges. Obviously, we should draw the edge table nodes with four vertices and five edges first. Since it is an undirected graph, it does not matter whether ivex is 0, jvex is 1 or vice versa, but ivex is set to be the same as the adjacent vertex subscripts for plotting purposes.

All right, so let’s analyze this graph

Firstedge is a pointer field that points to the first node of the edge table. Ivex and jvex are subscripts of the vertex coordinates attached to the edge. For example, 0 and 1 in the figure represent the edge between V0 and V1

So what are Ilink and Jlink?

Ilink refers to the next edge that ivex attaches to the vertex

Jlink refers to jvex attaching to the next edge of the vertex

An example is shown below:

If you look at the line above, Firstedge points to an edge, the vertex has the same index as ivex, and so on, vertex V0 has three edges associated with it, v0v1,v0v2,v0v3

So line 5,6 satisfies the goal of pointing to the next edge attached to the vertex v0, and the jvex of the node ilink points to must be the same as its own ivex value. Line 7 is the v1, v0 edge, which is the same thing as vertex v1 pointing to the next one after edge v1, v2. V2 has three attachments, so there are eight and nine after line 3. The vertex v3 on line 10 is the next edge after line 4.

There are 5 edges so there are 10 lines, as expected

An adjacency multiple list differs from an adjacency list only in that the same edge is represented by two nodes in an adjacency list, whereas in an adjacency multiple list there is only one node. To delete the edge (V0,V2) on the left, change the link point of ⑥⑨ on the right to ^. The implementation of the various basic operations is similar to the adjacency list

7.3.5 Number of side sets

An edge set consists of two one-dimensional arrays. One stores information about vertices; The other is to store information about edges. Each element of this edge array consists of an edge’s start index, end index, and weight

Examples are as follows:

The structure is easy to understand, just by looking at the picture