The concept of the figure

To quote from the encyclopedia:

In the branch Graph theory of mathematics, Graph is used to represent the relationship between objects and is the basic research object of Graph theory. A graph consists of small dots (called vertices or nodes) and the lines or curves (called edges) that connect them. Sylvester, a British mathematician, first coined the term “graph” in 1878.

We learned about the data structure of graphs, which is part of graph theory. So when you do not understand the content, it is suggested to read the relevant textbook of graph theory, may be able to solve your confusion.

Usually we use a binary expression representing an ordered pair: G=(V,E)G =(V,E)G =(V,E)G =(V,E)G =(V,E) to represent a graph structure, where VVV represents the set of vertices and EEE represents the set of edges:


E ⊆ { { x . y } : ( x . y ) ∈ V 2 . x indicates y } E \sube \lbrace \lbrace x, y \rbrace : (x, y) \in V^2 , x \ne y \rbrace

An edge set consists of all unordered pairs of vertices (in other words, edges connect pairs of vertices). For an edge {x,y}, the vertices x,y are said to be the endpoints of the edge, and the edge is said to connect the two points.

Relationships between vertices (edges)

There may be some kind of pairwise relationship between the vertices contained in the vertex set. If there is such a relationship between two points, we edge the two points, so that we get a member of the edge set, namely an edge. In a social network, the vertices are the users, and if the two users are connected by an edge, they are friends.

Undirected graph

If we use edges to represent friend relationships, friends in chat software can be regarded as two-way social networks. After all, we can chat only when we add friends, but not when we delete them. Such a graph with an undirected edge connecting two points is called an undirected graph.

Directed graph

Like the anchor in the short video, we can give him the following and double click on 666, and then the relationship can’t be represented by an undirected graph, because if we follow the anchor, the anchor doesn’t necessarily follow us, and if the anchor doesn’t follow us, then the relationship is one-way, using a directed edge to connect the two vertices. If we follow each other with the anchor, it can be regarded as an undirected graph friendship, but we can also use two directed edges to represent friendship. So when we study the data structure of graphs, we generally study directed graphs, because they can be used to represent undirected graphs.

Sparse and dense graphs

It is stated that when E

Vertex degree

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

Out degree and in degree

In directed graphs we see that there are directed edges that point to some vertex, that is, end at some vertex. There are directed edges that start at this vertex and point to other vertices, that is, start at one vertex.

So the number of directed edges that end at a vertex we call the entry of that vertex, and the number of directed edges that start at a vertex we call the exit of a vertex.

It is not difficult to see that in a digraph the degree of a vertex is equal to the sum of the degrees of out and in.

The storage structure of the graph

Before we can study the data structure of the graph, we need to learn a few things about how the graph is stored.

Adjacency matrix

Adjacency matrix is used to store the relation between the vertices of graph, which can be easily reflected by adjacency matrix.

Definition: If graph GGG has NNN vertices, denoted as: v1,v2… ,vnv_1,v_2,… ,v_nv1,v2,… ,vn, then construct a matrix AnnA_{nn}Ann of n∗nn * nn∗n order, and make it conform to such conditions: If (vi, vj) ∈ E (G) (v_i v_j) \ in E (G) (vi, vj) ∈ E (G), Aij = 1 a_ {ij} = 1 Aij = 1, otherwise the Aij = 0 a_ {{ij}} = 0 Aij = 0.

To understand this, consider the following graph:

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


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

Here’s how the matrix is constructed:

It can be understood by referring to this chart:

  1. When I = 1, j = 1, obviously v1v_1v1 has no edges of its own, so A11=0A_{11} = 0A11=0
  2. When I =1, j = 2, v1v_1v1 has edges to v2V_2v2, so A12=1A_{12} = 1A12=1
  3. When I =1, j = 3, v1v_1v1 has edges pointing to V3V_3v3, so A13=1A_{13} = 1A13=1
  4. When I = 1, j = 4, v1v_1v1 has no edges pointing to v4v_4V4, so A14=0A_{14} = 0A14=0
  5. When I = 2, j = 1, v2V_2v2 has no edge pointing to v1v_1v1, so A21=0A_{21} = 0A21=0
  6. When I = 2, j = 2, v2V_2v2 has no edges of its own, so A22=0A_{22} = 0A22=0
  7. When I = 2, j = 3, v2V_2V2 has no edge to v3V_3v3, so A23=0A_{23} = 0A23=0
  8. When I = 2, j = 4, v2V_2v2 has no edge pointing to v4v_4V4, so A24=0A_{24} = 0A24=0

. You can construct the matrix in this way

It can be seen that each row in the matrix, from top to bottom, represents the relationship between each vertex (A11,A21,A31 and A41A_{11}, A_{21}, A_{31} and A_{41}A11,A21,A31 and A41) and the other vertices. If you have an output relationship with a vertex, you put a 1 at that vertex.

Each column in the matrix, from left to right, represents the relationship between each vertex (A11,A12,A13, and A14A_{11}, A_{12}, A_{13}, and A_{14}A11,A12,A13, and A14) and the entry degree of the other vertices. If you have an input relationship with a vertex, you put a 1 at that vertex. In fact, we do a good job of the relationship out, in the relationship automatically marked.

Adjacency list

Adjacency list is also used to describe the relationship between vertices of a graph. It would look something like this in literal terms:

The adjacency list of an undirected graph is described as: A is adjacent to B, C; B is adjacent to a, C; C is adjacent to a and B.

In the case of a directed graph, the adjacency list shows the relationship between the degrees of each vertex, whereas the inverse adjacency list shows the relationship between the degrees of each vertex.

Taking the graph of adjacency matrix as an example, we can get the following description of adjacency list:

  1. V1v_1v1 is adjacent to V2, V3V_2, V_3V2,v3
  2. V2v_2v2 without adjacency
  3. The V3V_3V3 adjacency is v4V_4V4
  4. V4v_4v4 is adjacent to v2V_2v2

It would look something like this in linked lists:

v1->v2->v3

v2

v3->v4

v4->v2

The table heads of these lists are typically stored in an array for easy access to vertices.

The nice thing about adjacency lists is that it’s very easy to know which vertices a vertex is connected to.

Both adjacency matrix and adjacency list can be used to store graphs, and they have their own advantages and disadvantages. For example, for graphs with n vertices, adjacency matrix always needs n2n^2n2 storage space. When the number of edges is small, space will be wasted.

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

Construct a graph with an adjacency matrix

After theoretical study, let’s realize how to use adjacency matrix to store graphs.

/** * the structure of the graph *@param {*} Length Indicates the order of the adjacency matrix, that is, the number of vertices */
function Graph(length) {
  this.length = length;
  // Initializes a two-dimensional array of storage matrices
  this.matrix = [];
  for (let i = 0; i < length; i++) {
    // There is no need to convert the class array to an array
    this.matrix[i] = Array.from(new Int8Array(length)); }}Copy the code

After the structure of the graph is defined, let’s manually create an adjacency matrix, taking the graph of the adjacency matrix as an example.

/** * Inserts adjacency matrix data *@param {*} Graph drawing *@param {*} A 0- directed graph, 1- undirected graph *@param {*} I vertices are equal to the matrix subscript *@param {*} J vertices are the matrix subscript star@returns* /
function insert(graph, a, i, j) {
  if (i < 0 || i >= graph.n || j < 0 || j >= graph.n) {
    return;
  }
  // A digraph requires only one edge
  if (a === 0) {
    graph.matrix[i][j] = 1;
  } else {
    // An undirected graph has two sides, symmetric
    graph.matrix[i][j] = 1;
    graph.matrix[j][i] = 1; }}/** * outputs the adjacency matrix *@param {*} Figure * / 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 an 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 the code

This completes the creation and use of the adjacency matrix.

Adjacency lists are enough to build graphs

To construct an adjacency list, we need a linked list to hold vertices:

/** * Saves the list node * of vertices@param {*} Vertex vertex * /
function Node(vertex) {
  this.vertex = vertex;
  this.next = null;
}
Copy the code

Then we need the structure of the adjacency list, which has two attributes, one is the number of vertices in the graph, and the other is the array used to store the relationship between edges. The array stores the linked list with each vertex as the head node:

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

The next step is to create an adjacency list:

/** * insert nodes in reverse order *@param {*} Head Specifies the header *@param {*} The index points *@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 drawing *@param {*} A 0- directed side, 1- undirected side *@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 the code

Iterate over the output adjacency list

function outputGraph(graph) {
  let str = "";
  for (let i = 0; i < graph.length; i++) {
    str += i + ':';
    for (letj = graph.edges[i]; j ! = =null; j = j.next) {
      str += j.vertex + ' ';
    }
    str += '\n';
  }
  console.log(str);
}


const graph = new GraphList(4);
// Manually create an 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 the code