Theoretical basis of graph

This chapter introduces the basic concept of graph in data structure .

Catalog
1.  The basic concept of graph
2.  The storage structure of the graph

Reprint please indicate the source ： If the sky doesn't die - Blog Garden

More ： Data structure and algorithm series Catalog

The basic concept of graph

1. Definition of graph

Definition ： chart (graph) It's a little bit (vertex) The connection with these points (edge) Made up of ; among , Points are usually called " The vertices (vertex)", The connection between points is called " Edge or arc "(edege). It's usually written as ,G=(V,E).

2. Types of graphs

Depending on whether the edge has a direction , The graph can be divided into ： Undirected graph and Directed graph .

2.1 Undirected graph

The picture above G0 Is undirected graph , All edges of an undirected graph are undirected .G0=(V1,{E1}). among ,

(01) V1={A,B,C,D,E,F}. V1 By "A,B,C,D,E,F" A collection of several vertices .
(02) E1={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), (C,D),(E,F),(C,E)}. E1 By the side (A,B), edge (A,C)... And so on . among ,(A,C) Denotes by vertex A And vertex C Connected edges .

2.2 Directed graph

The picture above G2 It's a directed graph . Unlike an undirected graph , All edges of a digraph have directions ！ G2=(V2,{A2}). among ,

(01) V2={A,C,B,F,D,E,G}. V2 By "A,B,C,D,E,F,G" A collection of several vertices .
(02) A2={<A,B>,<B,C>,<B,F>,<B,E>,<C,E>,<E,D>,<D,C>,<E,B>,<F,G>}. E1 Is made up of vectors <A,B>, vector <B,C>... And so on . among , vector <A,B) By " The vertices A" Point to " The vertices C" The directed side of .

3. Adjacency point and degree

3.1 Adjacency point

Two vertices on an edge are called adjacency points .
for example , Undirected graph above G0 The summit of A And vertex C It's the adjacency point .

In a directed graph , Except for adjacency points ; also " Into the side " and " Out of the way " The concept of .
The entry edge of the vertex , Refers to the edge ending at this vertex . And the edge of the vertex , It refers to the edge starting from this vertex .
for example , There is a directed graph G2 Medium B and E It's the adjacency point ;<B,E> yes B Out of the way , still E The entry side of .

3.2 degree

In the undirected graph , The degree of a vertex is the edge adjacent to that vertex ( Or arc ) Number of .
for example , Undirected graph above G0 Middle peak A The degree is 2.

In a directed graph , Degrees and " The degree of " and " The degree of " Points .
The penetration of a vertex , Refers to the number of edges ending at this vertex . And the output of the vertex , Is the number of edges starting from this vertex .
The degree of the vertex = The degree of + The degree of .
for example , There is a directed graph G2 in , The vertices B My penetration is 2, The output is 3; The vertices B Degree =2+3=5.

4. Paths and loops

route ： If the vertex (Vm) To the top (Vn) There is a sequence of vertices between . said Vm To Vn It's a path .
The length of the path ： In the path " The number of sides ".
Simple path ： If vertices do not appear repeatedly on a path , It's a simple path .
loop ： If the first vertex of the path is the same as the last vertex , It's the loop .
Simple circuit ： The first vertex is the same as the last vertex , The other loops whose vertices do not repeat are simple loops .

5. Connected graphs and connected components

Connected graph ： For undirected graphs , There is an undirected path between any two vertices , The undirected graph is called a connected graph . For a directed graph , If there is a directed path between any two vertices in the graph , Then the directed graph is called strongly connected graph .

Connected component ： Each connected subgraph in a non connected graph is called the connected component of the graph .

6. power

I'm learning " Huffman tree " When , Read about " power " The concept of . The concept of weight in the figure is similar .

Above is a weighted graph .

The storage structure of the graph

I understand above " The basic concept of graph ", Now let's introduce the storage structure of the diagram . The storage structure of the graph , What is commonly used is " Adjacency matrix " and " Adjacency list ".

1. Adjacency matrix

Adjacency matrix refers to using matrix to represent graph . It uses a matrix to describe the relationship between vertices in the graph ( And the right of arc or edge ).
Suppose the number of vertices in the graph is n, Then the adjacency matrix is defined as ：

The following is a schematic diagram to explain .

In the picture G1 Is an undirected graph and its corresponding adjacency matrix .

In the picture G2 Is an undirected graph and its corresponding adjacency matrix .

Two arrays are usually used to realize adjacency matrix ： A one-dimensional array is used to store vertex information , A two-dimensional array to store edge information .
The disadvantage of adjacency matrix is that it consumes more space .

2. Adjacency list

Adjacency list is a chained storage representation of graph . It is improved " Adjacency matrix ", Its disadvantage is that it is not convenient to judge whether there is an edge between two vertices , But it saves more space than adjacency matrix .

In the picture G1 Is an undirected graph and its corresponding adjacency matrix .

In the picture G2 Is an undirected graph and its corresponding adjacency matrix .