The basis of the front-end data structure and algorithm graph

The basis of the front-end data structure and algorithm graph

Graph concept

To quote the description of Wikipedia:

In the branch graph theory of mathematics, Graph is used to express the relationship between objects and it is the basic research object of graph theory. A graph consists of small dots (called vertices or nodes) and straight lines or curves (called edges) connecting these dots. The English mathematician Sylvester first proposed the term "graph" in 1878.

It can be seen from the above that we learn the data structure of graphs, which is part of the content of learning graph theory. So when you encounter something that you don't understand, it is recommended to take a look at the relevant textbooks of graph theory, which may solve your confusion.

Usually we use a two-tuple expression representing an ordered pair:G=(V,E)G = (V, E) to represent a graph structure, whereVV represents the vertex set,EE represents the edge set:

E {{x,y}:(x,y)AV2,x y}E/sube/lbrace/lbrace x, y/rbrace: (x, y)/in V^2, x/ne y/rbrace

The edge set consists of all pairs of unordered vertices (in other words, the edges connect the pairs of vertices). For an edge {x, y}, the vertex x, y is said to be the end point of the edge, and the edge is said to connect these two points.

Relationship between vertices (edges)

There may be some pairwise relationship between the several vertices contained in the vertex set. If there is such a relationship between certain two points, we will connect the edges between these two points, so that we can get A member of the edge set is an edge. If it corresponds to a social network, the vertex is regarded as a user. If the two users are connected to an edge, it means that there is a friend relationship between them.

Undirected graph

If you use the side to represent the friendship, the friends in the chat software can be regarded as a two-way following social network. After all, you can chat only if you add a friend, and you can't chat if you delete it. This kind of graph connected by an undirected edge between two points is called an undirected graph.

Directed graph

Like the anchor in the short video, we can give him a point to double-click on 666. This relationship cannot be represented by an undirected graph. Because we have followed the anchor, the anchor will not necessarily follow us. If the anchor does not follow us, then this The relationship of is one-way, using a directed edge to connect two vertices. If we and the anchor follow each other, this can be regarded as an undirected friendship relationship, but we can also use two directed edges to represent the friendship relationship. So when studying the data structure of graphs, we generally study directed graphs because it can be used to represent undirected graphs.

Sparse and dense graphs

Regulations: When E<V lognE <V * logn , it is called a sparse graph, which means that there are few edges in the graph. Otherwise, it is called a dense graph. For example, if users pay attention to each other, then it is a dense graph.

Vertex degree

The degree of a vertex in the graph is calculated by how many edges a vertex has. For example, if a vertex has 3 edges, then the degree of this vertex is 3.

Out degree and in degree

In a directed graph, we will see that some directed edges point to a vertex, that is, a vertex is the end point. And some directed edges start from this vertex to other vertices, that is, take a certain vertex as the starting point.

In this way, the number of directed edges ending at a certain vertex is called the in-degree of the vertex, and the number of directed edges starting from a certain vertex is called the out-degree of the vertex.

It is not difficult to see that in a directed graph, the degree of a vertex is equal to the sum of the out degree and the in degree.

Graph storage structure

Before studying the data structure of the graph, we still have some prerequisite knowledge points to learn, in what way is the graph stored.

Adjacency matrix

The adjacency matrix is used to store the relationship between the vertices of the graph, and this relationship can be easily reflected through the adjacency matrix.

Definition: If the picture GGThe vertices of havenn , respectively marked as:v1,v2,...,vnv_1,v_2,...,v_n, Then construct a n nn * n th order matrixAnnA_{nn}, Let it meet this condition: if (vi,vj)AE(G)(v_i,v_j)/in E(G) ,Aij=1A_{ij} = 1 , otherwiseAij=0A_{{ij}} = 0 .

To understand through an example, suppose there is such a picture:

According to the definition of the adjacency matrix, the following matrix can be constructed:

[0110000000010100]\begin{bmatrix} 0 & 1 & 1 & 0/0 & 0 & 0 & 0/0 & 0 & 0 & 1/0 & 1 & 0 & 0/end{bmatrix}

Here is an explanation of how this matrix is constructed:

It can be understood against this chart:

  1. When i = 1, j = 1, it is obvious v1v_1I have no edges, so the matrix A11=0A_{11} = 0
  2. When i = 1, j = 2,v1v_1 Directed v2v_2 , So the matrix A12=1A_{12} = 1
  3. When i = 1, j = 3,v1v_1 Directed v3v_3 , So the matrix A13=1A_{13} = 1
  4. When i = 1, j = 4,v1v_1 No point v4v_4 , So the matrix A14=0A_{14} = 0
  5. When i = 2, j = 1,v2v_2 No point v1v_1 , So the matrix A21=0A_{21} = 0
  6. When i = 2, j = 2,v2v_2 I have no edges, so the matrix A22=0A_{22} = 0
  7. When i = 2, j = 3,v2v_2 No point v3v_3 , So the matrix A23=0A_{23} = 0
  8. When i = 2, j = 4,v2v_2 No point v4v_4 , So the matrix A24=0A_{24} = 0

...In this way, the matrix can be constructed

As you can see, each row in the matrix represents each vertex from top to bottom (A11,A21,A31withA41A_{11}, A_{21}, A_{31} and A_{41}) The relationship with the out-degree of other vertices. If there is an out-degree relationship with a certain vertex, mark 1 at a certain vertex.

Each column in the matrix represents each vertex from left to right (A11,A12,A13withA14A_{11}, A_{12}, A_{13} and A_{14}) The relationship with the in-degree of other vertices. If there is an in-degree relationship with a certain vertex, mark 1 at a certain vertex. In fact, after we have done a good job in the out-of-degree relationship, the in-degree relationship will be automatically marked.

Adjacency list

The adjacency list is also a tool used to describe the relationship between the vertices of the graph. If it is described in words:

There is such an undirected graph, its adjacency list is described as: a is adjacent to b, c; b is adjacent to a, c; c is adjacent to a, b.

If it is a directed graph, the adjacency table shows the relationship of the out-degree of each vertex, on the contrary, the inverse adjacency table shows the relationship of the in-degree of each vertex.

Taking the graph of the adjacency matrix as an example, the following description of the adjacency table can be obtained:

  1. v1v_1 Adjacent to v2,v3v_2,v_3
  2. v2v_2 No adjacency
  3. v3v_3 Adjacent to v4v_4
  4. v4v_4 Adjacent to v2v_2

If it is represented by a linked list, it is like this:

v1->v2->v3

v2

v3->v4

v4->v2

The header nodes of these linked lists are generally stored in an array to facilitate access to the vertices.

The advantage of the adjacency list is that it is easy to know which vertices are connected to a certain vertex.

Both the adjacency matrix and the adjacency list can be used to store the graph, and they have their own advantages and disadvantages. For example, for a graph with n vertices, the adjacency matrix is always needed n2n^2 storage space, when the number of sides is small, it will cause a waste of space.

Therefore, if it is a sparse graph, the adjacency table is generally used for storage, and if it is a dense graph, the adjacency matrix is used for storage.

Construct graph with adjacency matrix

After learning the theory, let's realize how to store the graph with the adjacency matrix.

/** * Chart structure * @param {*} length The order of the adjacency matrix, which is the number of vertices in the graph */ function Graph ( length ) { this .length = length; //Initialize the two-dimensional array that stores the matrix this .matrix = []; for ( let i = 0 ; i <length; i++) { //It can also be omitted here Convert the class array into an array this .matrix[i] = Array .from( new Int8Array (length)); } } Copy code

After defining the structure of the graph, let's manually create an adjacency matrix. Take the graph of the adjacency matrix as an example.

/** * Insert adjacency matrix data * @param {*} graph * @param {*} a 0-directed graph, 1-undirected graph * @param {*} i vertex, equivalent to matrix subscript * @param {*} j vertex, equivalent to matrix subscript * @returns */ function insert ( graph, a, i, j ) { if (i < 0 || i >= graph.n || j < 0 || j >= graph.n) { return ; } //A directed graph only needs one edge if (a === 0 ) { graph.matrix[i][j] = 1 ; } else { //An undirected graph has two edges, a symmetrical graph.matrix[i][j] = 1 ; graph.matrix[j][i] = 1 ; } } /** * Output adjacency matrix * @param {*} graph */ function output ( graph ) { let str = "" ; for ( let i = 0 ; i <graph.length; i++) { for ( let j = 0 ; j <graph.length; j++) { str += graph.matrix[i][j] + "" ; } str += "\n" ; } console .log(str); } const graph = new Graph( 4 ); //Manually create the adjacency matrix insert(graph, 0 , 0 , 1 ); insert(graph, 0 , 0 , 2 ); insert(graph, 0 , 2 , 3 ); insert(graph, 0 , 3 , 1 ); output(graph); console .log(graph); Copy code

This completes the creation and use of the adjacency matrix.

Use adjacency lists to create maps

To construct an adjacency list, we need a linked list for storing vertices:

/** * Save the linked list nodes of the vertices * @param {*} vertex vertex */ function Node ( vertex ) { this .vertex = vertex; this .next = null ; } Copy code

Then the structure of the adjacency list is needed. There are two attributes in the adjacency list. One is the number of vertices in the graph, and the other is an array for storing the relationship between the edges. The array stores a linked list with each vertex as the head node:

/** * Graph adjacency list structure * @param {*} length length */ function GraphList ( length ) { this .length = length; this .edges = []; for ( let i = 0 ; i <length; i++) { this .edges[i] = null ; } } Copy code

The next step is to create the adjacency list:

/** * Insert nodes in reverse order (the order of nodes does not matter) * @param {*} head * @param {*} index vertex * @returns reverse linked list */ function insertNode ( head, index ) { const node = new Node(index); node.next = head; head = node; return head; } /** * Create adjacency list * @param {*} graph * @param {*} a 0-directed edge, 1-undirected edge * @param {*} i vertex * @param {*} j vertex * @returns */ function insertGraph ( graph, a, i, j ) { if (i < 0 || i >= graph.length || j < 0 || j >= graph.length) { return ; } if (a === 0 ) { graph.edges[i] = insertNode(graph.edges[i], j); } else { graph.edges[i] = insertNode(graph.edges[i], j); graph.edges[j] = insertNode(graph.edges[j], i); } } Copy code

Traverse the output adjacency list

function outputGraph ( graph ) { let str = "" ; for ( let i = 0 ; i <graph.length; i++) { str += i + ':' ; for ( let j = graph.edges[i]; j !== null ; j = j.next) { str += j.vertex + '' ; } str += '\n' ; } console .log(str); } const graph = new GraphList( 4 ); //Manually create adjacency list for testing insertGraph(graph, 0 , 0 , 1 ); insertGraph(graph, 0 , 0 , 2 ); insertGraph(graph, 0 , 2 , 3 ); insertGraph(graph, 0 , 3 , 1 ); console .log(graph); outputGraph(graph); Copy code