2022.2.11

Today, I saw the following picture

A graph is a many to many data structure .

1、 Directed graph

1. Connecting two vertices is called an arc , Write it down as <v, w>, among v,w Is the vertex. ,v It's called the arc tail ,w It's called the arc head ,<v,w> It's called from vertex v The vertices w Arc of , Also known as v Adjacency to w, or w Adjacency from v.

2. A digraph has two degrees ： The degree of     At the top v Is the number of arc heads  .

                              The degree of     At the top v Is the number of arc tails .

2、 Undirected graph

1. Connecting two vertices is called an edge , Write it down as (v, w) or (w,v), because (v,w)=(w,v), among v,w Is the vertex. . It can be said that the vertex w And vertex v They are adjacency points to each other . edge (v, w) Attached to the apex w and v, Or in other words (v, w) And vertex v, w Related to .

2. The degree of an undirected graph ： And vertex v Number of sides associated .

3、 network

power ： Connecting the edges between two vertices weight.

Edges or arcs on a graph are called nets .

4、 connected 、 Connected graphs and connected components ; Strongly connected graph 、 Strong connected components

  In the undirected graph , If from the top v To the top w There is a path , said v and w It's connected . If the figure G Any two vertices in are connected , It's called a picture G It's a connected graph , Otherwise, it is called an unconnected graph . In undirected graph, the polar connected subgraph is called connected component . If a graph has n vertices , And the number of sides is less than n−1, The graph must be unconnected . Here's the picture (a) Shown , chart G 4  Be careful : Clarify connectivity 、 Connected graph 、 The concept of connected components is very important . First of all, we must distinguish polar Dalian connected subgraphs from minimal connected subgraphs , Polar Dalian tongsubgraphs are connected components of undirected graphs , Maximal means that the connected subgraph must contain all its edges ; A minimal connected subgraph is a subgraph that not only keeps the graph connected but also minimizes the number of edges . Yes 3 Connected components , Pictured （b） Shown .

 

Be careful : Clarify connectivity 、 Connected graph 、 The concept of connected components is very important . First of all, we must distinguish polar Dalian connected subgraphs from minimal connected subgraphs , Polar Dalian tongsubgraphs are connected components of undirected graphs , Maximal means that the connected subgraph must contain all its edges ; A minimal connected subgraph is a subgraph that not only keeps the graph connected but also minimizes the number of edges . 

Strongly connected graph 、 The definition of strongly connected component is the same as that of connected graph and connected component , But connected graphs and connected components are directed to undirected graphs , And strongly connected graphs 、 Strongly connected components are directed graphs .

The storage structure of the graph

One 、 Adjacency matrix

The adjacency matrix of a graph is stored in two arrays .

         A one-dimensional array stores vertex information in a graph ,

         A two-dimensional array ( It's called adjacency matrix ) Stores information about the edges or arcs in a graph .

Two 、 Adjacency list （ Undirected graph The vertices ）

The adjacency table of a graph is stored in an array , A linked list to represent the diagram .

         A one-dimensional array stores vertex information in a graph , Also record the value pin of the first adjacent contact ,

         A single linked list is used as the edge table .

Than Adjacency matrix saves space .

3、 ... and 、 Cross linked list （ Directed graph The vertices ）

Cross linked list is a chain storage structure of directed graph .

Four 、 Adjacency multiple tables （ Undirected graph edge ）

Adjacency multiple list is another chain storage structure of undirected graph .

5、 ... and 、 Edge set array

An edge set array is made up of two one-dimensional arrays . One is to store vertex information ; The other is the storage side of the information , Each data element of this edge array is subscripted by the starting point of an edge (begin)、 End subscript (end) And power (weight) form

To be specific, see (14 Bar message ) data structure ： chart (Graph)【 Detailed explanation 】_UniqueUnit The blog of -CSDN Blog _ Data structure chart

Shortest path

One 、 dijkstra ( Dijkstra ) Algorithm

1. Each time, the node that is farthest away from the starting point from the unlabeled node , Mark , Collect the best path .

2. Calculate the newly added node A Adjacent nodes of B Distance of , if （ node A+A To B Distance of ）< node B The distance will be updated B The distance between points and B Dot Precursor point （ In order to trace back the path ）.

Two 、 Freud ( Floyd ) Algorithm

Find the middle vertex of two vertices ：

For each vertex v And any vertex pair （i,j）（i！=j！=v）

If A[i][j]（ An array of record weights ）>A[i][v]+A[v][j]

==>A[i][j]=A[i][v]+A[v][j]

path[i][j]（ Record an array of intermediate vertices ）=v;