This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

The storage structure of the graph

3. Cross linked lists

A cross linked list is a chain storage structure of a digraph. In a cross linked list, there is one node corresponding to each arc of the digraph and one node corresponding to each vertex. Node structure is as follows:

Arc node has 5 domains:

The position of arc tail, the position of arc head, the next arc with the same arc head, the next arc with the same arc tail and the information of this arc

The vertex node has three domains: the data domain of the vertex, the first arc node with the vertex as the arc head, and the first arc node with the vertex as the arc tail

Definition of the storage structure of a digraph linked list

#define  MaxVertexNum  100          // The maximum number of vertices in the graph
typedef  struct  ArcNode{                 // Side table node
int  tailvex,headvex;
struct  ArcNode  *hlink, *tlink; 
//InfoType info
}ArcNode;
typedef  struct  VNode{                   // Vertex table node
VertexType  data;
ArcNode  *firstin,*firstout;
}VNode;
typedef  struct{
VNode  xlist[MaxVertexNum];   / / adjacency list
int  vexnum,arcnum;                    // The number of vertices and arcs in the graph
}GLGraph;
Copy the code

4. Adjacency multiple table

Adjacency multiple list is a chain storage structure of undirected graph. In adjacency multiple list, there is one node corresponding to each edge of undirected graph and one node corresponding to each vertex. Node structure is as follows:

Side node has 5 fields:

Ilink points to the next edge attached to vertex ivex, jlink points to the next edge attached to vertex jvex, info stores the necessary information

The vertex node has two fields: the data field of the vertex of the data table, and the firstedge indicates the firstedge attached to the vertex

Definition of an adjacent multiple list storage structure for an undirected graph

#define  MaxVertexNum  100         Typedef struct ArcNode{// side table node
int  ivex,jvex;
struct  ArcNode  *ilink, *jlink; 
//InfoType info;
}ArcNode;
typedef  struct  VNode{                    // Vertex table node
VertexType  data; 
ArcNode  *firstedge;
}VNode;
typedef  struct{
VNode  adjmulist[MaxVertexNum];    / / adjacency list
int  vexnum,arcnum;                              // The number of vertices and edges
}AMLGraph;
Copy the code

Expand the material

7.2.3 Cross linked list

A cross linked list is another chain storage structure of a digraph, which can be regarded as the combination of adjacency list and inverse adjacency list, that is, each arc in a digraph corresponds to an arc node in a cross linked list, and each vertex corresponds to a vertex node in a cross linked list. Figure 7-12 shows the structure of the two types of nodes.

Figure 7-12 Structure of arc nodes and vertex nodes in a cross – character list

There are five domains in the arc node: tailvex and headvex indicate the position of the two vertices in the graph respectively, chain domain hnext points to the next arc with the same arc head, chain domain tnext points to the next arc with the same arc tail, and info points to the relevant information of the arc. Arcs with the same head are on the same linked list, and arcs with the same tail are on the same linked list. Their head node is the vertex node, which consists of three domains: data domain stores information related to vertices, such as vertex names; Firstin and firstout are two chain fields that point to the first arc node with the vertex as the arc head or arc tail, respectively. In a cross linked list, the linked list in which arc nodes are located is non-cyclic, and the relative positions between nodes are formed naturally, not necessarily sorted by vertex sequence number. The head node, the vertex node, is the sequential storage.

If a directed graph is a sparse graph, then its adjacency matrix must be a sparse matrix, and a cross linked list can also be regarded as a linked list storage structure of adjacency matrix. Figure 7-13 shows a cross – character list of digraphs.

Figure 7-13 Cross chains of digraphs indicate intent

The structure of a digraph is described as follows.

In a cross linked list, it is easy to find both arcs with vi as the tail and arcs with vi as the head, so it is easy to find the out and in degrees of vertices. In some directed graph applications, a cross – linked list is a very useful tool.

7.2.4 Adjacency multiple list

Adjacency multiple list is another storage structure of undirected graphs. Because if an adjacency list is used to store an undirected graph, the two edge nodes of each edge are in a linked list headed by the two vertices attached to the edge, which makes some operations of the graph inconvenient. For example, to mark an edge that has been visited, or to delete an edge in the graph, you need to find two nodes that represent the same edge. Therefore, it is more suitable to use adjacency multiple list as storage structure in the problem of undirected graph.

The storage structure of an adjacent multiple list is similar to that of a cross linked list. It is also composed of a vertex list and an edge list. Each edge is represented by a node.

Figure 7-14 Node structure of an adjacent multiple list

The vertex table consists of two fields, data field stores information related to the vertex, and firstedge field indicates the firstedge attached to the vertex. The edge table node consists of six fields: mark is the mark field, which can be used to mark whether the edge has been searched; Ivex and jvex are the positions of the two vertices attached to the edge in the graph; Inext points to the next edge attached to the vertex ivex; Jnext points to the next edge attached to the vertex jvex; Info is a field of Pointers to various edge-related information.

Figure 7-15 shows the adjacency multiple list of an undirected graph.

Figure 7-15 Adjacency multiple representation intention of an undirected graph

All edges attached to the same vertex in the adjacency multiple list are connected in series in the same linked list. Since each edge is attached to two vertices, each edge node is linked in two linked lists at the same time. It can be seen that for an undirected graph, the difference between the adjacency multiple-list and the adjacency list is that the same edge is represented by two nodes in the adjacency list, while in the adjacency multiple-list there is only one node.

Therefore, an adjacency multiple list requires the same amount of storage as an adjacency list, except for adding a flag domain to the edge node. In the adjacency multiple list, the implementation of various basic operations is similar to the adjacency list. The form of the adjacency multilist structure is described below.