“This is the 25th day of my participation in the August Gwen Challenge.

Follow me for more updates

Data structures and algorithms (I): time complexity and space complexity

Data structure and algorithm (two): stack

Data structures and algorithms (iii): queues

Data structures and algorithms (4): single linked lists

Data structures and algorithms (5): bidirectional linked lists

Data structures and algorithms (6): hash table

Data structures and algorithms (7): trees

Data structure and algorithm (8): sorting algorithm

Data structures and Algorithms (9): Classical algorithms interview questions

Data structures and algorithms (10): recursion

Data structures and Algorithms (xi): graphs

The previous article introduced two types of graph storage: adjacency matrix and adjacency list. This article continues to introduce other graph storage structure: inverse adjacency list and cross linked list.

1. Inverse adjacency list

For directed graphs, the defect of adjacency list is that to query the entry degree of a vertex, the whole list needs to be traversed, so the inverse adjacency list is introduced. Inverse adjacency list: The number of edge nodes under any table head node is the number of arcs in the graph for that node, as opposed to adjacency list. The adjacency list of a graph reflects the out-degree adjacency of nodes, while the inverse adjacency list of a graph reflects the in-degree adjacency of nodes.
A. Inverse adjacency list

In the graph, the nodes that point to vertex V1 are V0 and V3, so in the inverse adjacency list, the vertices corresponding to vertex V1 are subscripts 0 and 3

2. Cross linked lists (for directed graphs)

For directed graphs, the defect of the adjacency list is that it is necessary to traverse the entire list to query the entry degree of a vertex, while the inverse adjacency list traverses the entire list to query the exit degree of a vertex. So we introduce a cross linked list, a cross linked list is a list structure formed by combining adjacency list and inverse adjacency list. The basic idea is to add an entry list on the basis of the exit list of adjacent linked list. Application scenarios of a cross-linked list: When the input and output of a vertex are frequently calculated, or whether a vertex is the adjacency or inverse adjacency of another vertex, the storage mode of a cross-linked list is needed.
B. Cross linked lists store directed graphs

Note: the green arrow represents adjacency and the red arrow represents inverse adjacency

A cross linked list is composed of two kinds of nodes: VertexNode and EdgeNode.

  • VertexNode consists of data, FirstAdjin, and FirstAdjOut.
    • Data: A data field that stores data information about vertices.
    • Firstadjin: a pointer to the first node of the entry table for this vertex;
    • Firstedgeout: An edge header pointer that points to the first node of the edge list for this vertex (firstedgeout is the same as in adjacency lists).
  • EdgeNode is composed of tailvex, Headvex, Taillink and HeadLink.
    • Tailvex and headvex: respectively represent the subscripts of arc starting point and arc ending point in the vertex table;
    • Taillink: the edge table pointer field of the starting point of arc, pointing to the next node in the edge table of the starting point of arc, that is, pointing to the next edge that is the same as the starting point of this edge;
    • Headlink: pointer field of the entry list of the end point of an arc, pointing to the next node in the entry list of the end point of an arc, that is, pointing to the next edge that is the same as the end point of this edge;
    • Weight: Indicates the weight of this edge (not required for non-mesh diagrams)
Typedef struct VertexNode{int data; EdgeNode* firstadjin; EdgeNode* firstadjout; }; Typedef struct EdgeNode{int tailvex; int headvex; int weight; EdgeNode* headlink; EdgeNode* taillink; };Copy the code

In the illustration of a cross linked list:

  • There are two arcs starting from v0 :

    and

    , so there are two edges in the edge table of V0, that is, firstedgeOut of VertexNode points to the firstedge table node

    , and taillink of

    points to

    , that is, the edge table of V0

    — >

    ; (See the red arrow)
    ,v2>
    ,v1>
    ,v2>
    ,v1>
    ,v1>
    ,v2>
    ,v1>
  • There are two arcs ending at v1 :

    and

    , so there are two edges in the edge entry table of V1, that is, firstedgeIn of VertexNode points to the firstedge table node

    , and then the headlink of

    points to

    , that is, the edge entry table of V1 is Like this: < where v0, v1 > — > < where v0, v3 >; (See the green arrow)
    ,v3>
    ,v1>
    ,v1>
    ,v1>
    ,v1>

Pay attention to my

If you think I write well, please click a like to pay attention to me, your support is my biggest motivation!