The basic concept

Graph=(V, E) Graph=(V, E) Graph=(V, E) Graph=(V, E) Graph

1.1 directed graph

In a directed graph, the vertices <x, y> are ordered, <x, y> is a directed edge from vertex x to vertex Y, vertex X is the starting point, vertex y is the ending point, <x, y> and <y, x> are two different edges, c in the figure above is a directed graph. Its vertex set V (c) = {0}, edge collection of E (c) = {< 0, 1 >, < 1, 0 >, < 1, 2 >}.

1.2 the undirected graph

In an undirected graph, the vertex pairs (x,y) are unordered, (x,y) and (y,x) are the same edge, and a in the figure above is an undirected graph, Its vertex set V (a) = {0, 1, 2, 3}, the edge of its collection of E (a) = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}.

When discussing graphs in this chapter, there are two types of graphs beyond the scope of discussion: one is a graph whose vertices are connected to themselves; the other is a graph in which there are multiple edges between vertices in an undirected graph. The structure of the two graphs is as follows

1.3 complete graph

An undirected graph with n vertices and n(n-1)/2 edges is an undirected complete graph. A directed graph with n vertices and n(n-1) edges is a directed complete graph. The structure of the two graphs is as follows

1.4 the right to

An edge has a value associated with it, which represents the distance from one vertex to another, the time spent, and this value is called the weight.

1.5 Adjacency Vertices

In an undirected graph, if an edge is (u,v), then u and V are adjacent vertices to each other. In a directed graph, if an edge is an edge, then vertex U is adjacent to vertex V, and vertex V is adjacent to vertex U.

1.6 subgraph

Taking the undirected perfect diagram in 1.3 as an example, the following diagram shows several of its subgraphs

1.7 degrees

The number of edges associated with vertex V is called the degree. In a directed graph, the number of directed edges ending in V is the inbound degree of V, the number of directed edges starting at v is the outbound degree, and the degree of V is the sum of inbound degree and outbound degree.

1.8 the path

Starting at vertex vi, I follow some edges through VP1, VP2… When VPM reaches vj, it is called (vi, vp1, vp2… VPM, vj) is a path from vertex vi to vj.

1.9 Path Length

For an unweighted graph, the path length refers to the number of edges on the path. In fact, for an unweighted graph, the weight of the edges can be considered to be 1; For a weighted graph, the path length is equal to the sum of the weights of the edges along the path.

1.10 Connected graphs and connected components

An undirected graph is said to be connected if any two vertices are connected. The maximally connected subgraph of an unconnected graph is called a connected component.

In an unconnected graph, starting from a vertex, depth first or breadth first cannot traverse all the vertices of the graph, but can only access all the vertices of the maximum connected subgraph where the vertex is located, which constitute a connected component.

In a connected graph, there is only one connected component, while in an unconnected graph, there are multiple connected components. The graph shown below is an unconnected graph with two connected components, which are {0,1,2,3}, {5,6} respectively.

1.11 Strongly Connected graphs and strongly connected components

In a directed graph, any two points (x, y) are connected, that is, there are and. Then the graph is a strongly connected graph and a non-strongly connected graph, which is composed of multiple strongly connected subgraphs. The maximal strongly connected subgraph of a non-strongly connected graph is called a strongly connected component.

1.12 spanning tree

The spanning tree of an undirected connected graph is its minimal connected subgraph. The minimum here refers to the minimum number of edges. If the graph has N vertices, its spanning tree is composed of N-1 edges.

2. Diagram storage structure

2.1 Adjacency matrix representation

The structure of an undirected connected graph is shown below

The adjacency matrix is a two-dimensional array. The structure of the graph in the figure above can be represented by the following two-dimensional array

var max_value = 9999;
var maps = [
    [0,  28, max_value, max_value, max_value,  10, max_value],
    [28, 0, 16, max_value, max_value,max_value, 14 ],
    [max_value, 16, 0, 12, max_value, max_value, max_value],
    [max_value, max_value, 12, 0, 22, max_value, 18],
    [max_value, max_value, max_value, 22, 0, 25, 24],
    [10, max_value, max_value, max_value, 25, 0, max_value],
    [max_value, 14, max_value, 18, 24, max_value, 0]
];
Copy the code

For maps [I] [j] :

  • If I ==j then maps[I][j]=0
  • If I! Maps [I][j] =j, if (I,j) exists or < I,j> exists, then maps[I][j] equals the weight from I to j
  • If I! Maps [I][j] = max_value if (I,j) does not exist or < I,j> does not exist then maps[I][j] = max_value.

2.2 Adjacency list representation

Although the adjacency matrix can represent the structure of the graph, it has defects. If the number of vertices in the graph is very large while the number of edges is very small, the matrix will become very sparse and the storage efficiency will be low. At this time, the data can be stored in the form of adjacency list

If the graph is stored in the form of an adjacency list, the join list is structured as follows

Nodetables are represented by arrays, and outbound tables are represented by linked lists

3. Graph traversal

Graph traversal has two methods, one is depth-first traversal, the other is breadth-first traversal, in fact, when learning trees, we have been exposed to these two traversal methods, the search process of binary search tree is depth-first traversal, and the hierarchical printing binary tree is breadth-first traversal. To describe these two traversal methods, we first give a general class definition for storing graphs with an adjacency matrix

const Queue = require("./queue"); var max_value = 9999; function Graph(){ var maps = []; var node_num = 0; var edge_num = 0; this.init = function(input_maps){ maps = input_maps; node_num = this.get_node_num(); edge_num = this.get_edge_num(); }; This.get_node_num = function(){if(node_num! =0){ return node_num; } return maps.length; }; This. get_edge_num = function(){if(edge_num! =0){ return edge_num; } var count = 0; for(var i = 0; i < node_num; i++){ for(var j = i+1; j< node_num; j++){ if(maps[i][j]>0 && maps[i][j]<max_value){ count++; } } } return count; }; This. get_weight = function(u, v){return maps[u][v]; }; };Copy the code

Take the weighted undirected connected graph in 2.1 for example

Nodetables are represented by arrays, and outbound tables are represented by linked lists

3. Graph traversal

Graph traversal has two methods, one is depth-first traversal, the other is breadth-first traversal, in fact, when learning trees, we have been exposed to these two traversal methods, the search process of binary search tree is depth-first traversal, and the hierarchical printing binary tree is breadth-first traversal. To describe these two traversal methods, we first give a general class definition for storing graphs with an adjacency matrix

const Queue = require("./queue"); var max_value = 9999; function Graph(){ var maps = []; var node_num = 0; var edge_num = 0; this.init = function(input_maps){ maps = input_maps; node_num = this.get_node_num(); edge_num = this.get_edge_num(); }; This.get_node_num = function(){if(node_num! =0){ return node_num; } return maps.length; }; This. get_edge_num = function(){if(edge_num! =0){ return edge_num; } var count = 0; for(var i = 0; i < node_num; i++){ for(var j = i+1; j< node_num; j++){ if(maps[i][j]>0 && maps[i][j]<max_value){ count++; } } } return count; }; This. get_weight = function(u, v){return maps[u][v]; }; };Copy the code

Take the weighted undirected connected graph in 2.1 for example

3.1 Depth-first traversal

Different from tree traversal, points in the graph may be interconnected. In order to avoid repeated traversal, points that have been traversed must be identified. The array visited[I]=1 is used in the example to indicate that I has been traversed. By default, tree traversal starts from root node, and graph does not have the concept of root node. Therefore, in traversal, start vertex V should be specified, find all vertices that V can connect, traverse these vertices, and do the same operation to these vertices as V.

var graph_dfs = function(v, visited, component){ visited[v] = 1; // indicates that v has accessed console.log(v); component.push(v); var row = maps[v]; for(var i=0; i<row.length; I ++){if(row[I]<max_value && visited[I]==0){// vis connected to I, and I is not traversed yet; }}}; This. DFS = function(v){var visited = new Array(node_num); var component = []; For (var I =0; i<node_num; i++){ visited[i] = 0; } graph_dfs(v, visited, component); return component; };Copy the code

3.2 Breadth first traversal

The array visited[I]=1 is also used to indicate that I has been traversed. Just like the hierarchical printing node of the tree, it is necessary to put other vertices that can be connected by vertex V into the queue by means of a queue, and then exit the queue, and do the same operation as V for the vertex that has just been queued

var graph_bfs = function(v, visited, component){ var queue = new Queue.Queue(); queue.enqueue(v); visited[v] = 1; // indicates that v has accessed console.log(v); component.push(v); while(! queue.isEmpty()){ var visited_v = queue.dequeue(); var row = maps[visited_v]; for(var i=0; i<row.length; I ++){if(row[I]<max_value && visited[I]==0){// vis connected to I, and I is not traversed. visited[i] = 1; // indicates that v has accessed console.log(I); component.push(i); }}}}; this.bfs = function(v){ var visited = new Array(node_num); var component = []; for(var i=0; i<node_num; i++){ visited[i] = 0; } graph_bfs(v, visited, component); return component; };Copy the code

3.3 Connected Components

The diagram below is an unconnected graph

A graph can have multiple mutually connected subgraph, also there are multiple connected components, such as from 1 began to traverse the figure, will get a connected components, and starting from July, will get a connected components, then the concrete from which started yet, you are not sure, so the figure in the storage structure and no logo several connected components as well as all the vertices in the connected components.

Therefore, to detect all vertices, if they have already been visited, then the point must fall on the connected component of the graph already obtained, otherwise, another connected component can be obtained by triggering traversal of the graph from this vertex

this.components = function(){ var visited = new Array(node_num); var component_lst = []; for(var i=0; i<node_num; i++){ visited[i] = 0; } for(var i=0; i<node_num; i++){ if(visited[i]==0){ var component = []; graph_bfs(i, visited, component) component_lst.push(component); } } return component_lst; };Copy the code

4. Minimum spanning tree

Every spanning tree in the connected graph is a maximal acyclic subgraph of the original graph. If any edge is deleted, the spanning tree is no longer connected. If an edge is added, a loop will be formed.

A graph has many spanning trees, and different spanning trees have different sum of weights. The spanning tree with the smallest sum of weights is called the minimum spanning tree, which can solve the path planning problem.

Assuming that a communication network is established between N cities, at least N-1 routes need to be set up. If the cost of establishing a communication line between any two cities has been determined, how to plan the route so that the cost is the lowest? The diagram in 2.1 is still used here

Each vertex represents a city, and the weight represents the cost of construction, so how do you plan the route?

4.1 Kruskal algorithm

Kruskal algorithm and Huffman tree generation algorithm is very similar to that of all the edges in first to a minimum in the heap, unavailability do key value, then the edge on the top of the heap, and will be used by at least a minimum spanning tree, so will pile top removed into the minimum spanning tree, now, pile top is the rest of the edge weights in the smallest, continue to delete and add to the minimum spanning tree.

In the process of repeatedly removing the edge at the top of the heap and adding it to the minimum spanning tree, it is necessary to determine whether the two vertices of the edge are in the same connected component. If so, the edge cannot be used, otherwise it will form a loop.

Why does this allow you to create a minimum spanning tree? If the edge (0,5) is not in the minimum spanning tree, then it must be the other two edges that connect vertices 0 and 5 to the minimum spanning tree. However, the edges (0,5) are the least weighted edges that can be found. If the weights of the two edges assumed above are greater than 10, So it’s obviously better to use 0,5, but what if the weights of the two edges I assumed were equal to 10? (0, 5) this side does not in the minimum spanning tree, but when you select the other two edges are vertex 0 and 5 to the minimum spanning tree, you still follows the minimum edge selection this rule, and the selection of the other two side still face (0, 5), on the edge of the problem, so, always choosing a side with minimum weight, The minimum spanning tree must be built. Below is the process of building a minimum spanning tree

In the process of building from graph D to graph E, the distance from vertex 3 to vertex 6 is 18, less than 22 from vertex 3 to vertex 4. However, if the edge from 3 to 6 is selected, a loop will be formed to determine whether the two vertices are in the same connected component. You can use and look up the set

const MinHeap = require("./minheap"); const UFSets = require("./ufset"); const Graph = require("./graph"); var max_value = 9999; var Edge = function(head, tail, cost){ this.head = head; this.tail = tail; this.cost = cost; }; function kruskal(graph){ var mst = []; var node_num = graph.get_node_num(); var edge_num = graph.get_edge_num(); var min_heap = new MinHeap.MinHeap(edge_num); var ufset = new UFSets.UFSets(node_num); for(var i = 0; i < node_num; i++) { for (var j = i + 1; j < node_num; j++) { var cost = graph.get_weight(i, j); if(graph.get_weight(i, j) ! = max_value){ var ed = new Edge(i, j, cost); min_heap.insert(ed); } } } var count = 1; while(count<node_num){ var ed = min_heap.remove_min(); var head_root = ufset.find(ed.head); var tail_root = ufset.find(ed.tail); if(head_root ! = tail_root){ ufset.union(head_root, tail_root); mst.push(ed); count++; }else{console.log(" loop "); console.log(ed); } } return mst; }; var maps = [ [0, 28, max_value, max_value, max_value, 10, max_value], [28, 0, 16, max_value, max_value,max_value, 14 ], [max_value, 16, 0, 12, max_value, max_value, max_value], [max_value, max_value, 12, 0, 22, max_value, 18], [max_value, max_value, max_value, 22, 0, 25, 24], [10, max_value, max_value, max_value, 25, 0, max_value], [max_value, 14, max_value, 18, 24, max_value, 0] ]; var graph = new Graph.Graph(); graph.init(maps); var mst = kruskal(graph); console.log(mst);Copy the code

The final output of the program is

Loop {head: 3, tail: 6, cost: 18} Loop {head: 4, tail: 6, cost: 24} [{head: 0, tail: 5, cost: 10}, {head: 2, tail: 3, cost: 12 }, { head: 1, tail: 6, cost: 14 }, { head: 1, tail: 2, cost: 16 }, { head: 3, tail: 4, cost: 22 }, { head: 4, tail: 5, cost: 25 } ]Copy the code

4.2 prim algorithm

The Prim algorithm requires specifying a vertex V from which to build a minimum spanning tree. Similar to Kruskal algorithm, it also needs a minimum heap memory edge, the memory graph edge, vertex V is the first vertex added to the minimum spanning tree vertex set, denoted b_mst[v]=1.

With array b_mst said [I] = 1 vertex in the minimum spanning tree I set, every time an endpoint in the spanning tree are selected, and the other one endpoint is not the value minimum spanning tree of the edge (u, v), and it happens to be on the top of the heap, it is removed from the minimum heap, and add to the spanning tree, then all will be the emergence of new one endpoint in the spanning tree, Another edge whose endpoint is not in the spanning tree is added to the minimum heap, and so on until n-1 edges are found.

Why does this create a minimum spanning tree? Taking vertex 1 as an example, when the minimum spanning tree is created based on vertex 1, the cost of selecting (1,6) is the minimum. Based on this, the cost of selecting (1,2) is the minimum when the minimum spanning tree is created. And so on, the cost of each step is the minimum, so a minimum spanning tree will be generated eventually.

Suppose that after (1,6) is selected, instead of (1,2), (6,3) is selected. Although the weight of (6,3) is higher, is it possible that the following steps can be selected with lower weight than that of (1,2) due to path changes, so that a smaller spanning tree can be generated? The answer is no, because vertex 2 is going to be added to the minimum spanning tree after all, so if we use (1,2), we can only use (2,3), but then the weight of (2,3) plus (6,3) must be greater than the weight of (1,2) plus (2,3), not the weight of (1,2),(2,3). Here is the process of creating a minimum spanning tree using prim:

Sample code:

const MinHeap = require("./minheap"); const Graph = require("./graph"); var max_value = 9999; var Edge = function(head, tail, cost){ this.head = head; this.tail = tail; this.cost = cost; }; Function prim(graph, v){var MST = []; var node_num = graph.get_node_num(); var edge_num = graph.get_edge_num(); var b_mst = new Array(node_num); For (var I =0; i<node_num; i++){ b_mst[i] = 0; } b_mst[v] = 1; var count = 1; var start_v = v; var min_heap = new MinHeap.MinHeap(edge_num); While (count < node_num){for(var I = 0; i < node_num; i++) { if(b_mst[i]==0){ var cost = graph.get_weight(start_v, i); if(cost ! = max_value){ var ed = new Edge(start_v, i, cost); min_heap.insert(ed); } } } while(min_heap.size()! =0){ var ed = min_heap.remove_min(); If (b_mst[ed.tail] == 0){mst.push(Ed); start_v = ed.tail; B_mst [start_v] = 1; count++; break; } } } return mst; }; var maps = [ [0, 28, max_value, max_value, max_value, 10, max_value], [28, 0, 16, max_value, max_value,max_value, 14 ], [max_value, 16, 0, 12, max_value, max_value, max_value], [max_value, max_value, 12, 0, 22, max_value, 18], [max_value, max_value, max_value, 22, 0, 25, 24], [10, max_value, max_value, max_value, 25, 0, max_value], [max_value, 14, max_value, 18, 24, max_value, 0] ]; var graph = new Graph.Graph(); graph.init(maps); var mst = prim(graph, 1); console.log(mst);Copy the code

5. Shortest path problems

The traffic network can be regarded as a weighted graph. The following figure represents a piece of road network. The vertex is the intersection, and the weight value on the edge is the time needed to get from one intersection to another.

Dijkstra algorithm generates the shortest path step by step in ascending order of path length. It can calculate the shortest distance from the starting point to other points. There are two basic things you need to know about Dijkstra

  • If there is A shortest path AB from A to B, and C happens to be on that path, then the subpath AC of AB must be the shortest path from A to C

    If there is A subpath AC that is not the shortest, then there is an even shorter path from A to C called ‘AC ‘, then ‘AC+CB ‘is less than AB, so AB is not the shortest path, contradicting the hypothesis.

  • Starting from vertex 1, we can get to vertex 2, 3, 4, 5, and the path length is 7, 7, 2, 2 respectively. Among them, the length to vertex 4 and 5 is 2, which is the shortest path to reach the vertex. Then we can determine that the shortest path length from vertex 1 to vertex 4 is 2. The shortest path length to vertex 5 is 2. Whether the path length to vertex 3 and 2 is the shortest is not confirmed at present. The principle is that the length of the path from vertex 1 to vertex 4 is already the smallest of the weights of the edges from vertex 1, and any other path, the length of the path is greater than 2. Could not determine whether the path length of vertex 1 to 3 the shortest, because you can start from vertices 1 through like vertex 4 vertex around a circle to 3, figure, for example, starting from the vertices 1, after vertex 4, 7 to 3, the path length is 6, less than directly from the vertex 1 directly to 3.

To illustrate the algorithm, we use a dictionary to represent a graph structure

Var graph_dict = {" 0 ": {" 5" : 2, "4" : 3}, / / can be from 0 to 5, a weight of 2, 0 to 4, a weight of 3 "1" : {7, "2" : "3" : 7, "4" : 2, "five" : 2}, "2" : {8, "8" : "6", 7 "1" : 7}, "3" : {" 6 ": 2," 10 ": 3," 7 ": 1," 1 ": 7}," 4 ": {" 1" : 2, "7" : 3, "0", 3}, "5" : {10, "14" : "1" : 2, "0", 2}, "6" : {" 9 ": 1, "12" : 4, "3" : 2, "2" : 7}, "7" : {" 3 ": 1," 11 ": 2," 4 ": 3}," eight ": {" 9" : 4, "2" : 8, "14" : 1}, "9" : {9, "13" : "6" : 1, "eight" : 4}, "10" : {" 12 ": 6," 11 ": 8," 3 ", 3}, "11" : {" 10 ": 8," 7 ": 2}," 12 ": {" 13" : 2, "10" : 6, "6" : 4}, "13" : {" 12 ": 2," 9 ": 9}};Copy the code

The algorithm idea for calculating the shortest distance from vertex V to the other vertices is as follows: Use the array v_arr to store vertices whose shortest path length has been found, use the dictionary dis to store the shortest path length of vertex V to each vertex, use path to store the shortest path first, initialize dis, set the distance from vertex V to each vertex INF=9999

In the second step, starting from vertex V, centering on vertex V, find the vertices that can be reached and their path length, then update dis and add vertex V to v_ARr

In the third step, from the rest of the vertex finds from the vertex v recently w, then w centered outward looking for all the vertices and the path length can reach, and updates the dis, and join the v_arr will w, it is not hard to see, to the operation of the vertex w operation and v is the same, find the v in the vertex w is equivalent to the second step, recycling the process, Until all vertices are stored in v_ARR.

The next shortest path is always found in the shortest path formed by extending an edge from an existing shortest path. Since each cycle starts from the nearest vertex to v, and dis is updated each time, dis ultimately keeps the shortest path length of vertex V to all vertices.

For vertex 0, for example, to reach its peak have 5 and 4, and the known vertex 1 to 4 and 5 of the shortest path length is 2, then with vertex 4 for the new center will find vertex 0, to find the shortest path and vertex 4 to 0 of the shortest path is 3, then the vertex 1 to 0 of the shortest path length is 2 + 3 = 5. When looking for the shortest path outward from the center of vertex 5, vertex 0 will also be found, and the shortest distance from vertex 5 to vertex 0 is 2, then the shortest path length from vertex 1 to vertex 0 is 2+2=4, smaller than 5, so dis is updated. The sample code

Var graph_dict = {" 0 ": {" 5" : 2, "4" : 3}, / / can be from 0 to 5, a weight of 2, 0 to 4, a weight of 3 "1" : {7, "2" : "3" : 7, "4" : 2, "five" : 2}, "2" : {8, "8" : "6", 7 "1" : 7}, "3" : {" 6 ": 2," 10 ": 3," 7 ": 1," 1 ": 7}," 4 ": {" 1" : 2, "7" : 3, "0", 3}, "5" : {10, "14" : "1" : 2, "0", 2}, "6" : {" 9 ": 1, "12" : 4, "3" : 2, "2" : 7}, "7" : {" 3 ": 1," 11 ": 2," 4 ": 3}," eight ": {" 9" : 4, "2" : 8, "14" : 1}, "9" : {9, "13" : "6" : 1, "eight" : 4}, "10" : {" 12 ": 6," 11 ": 8," 3 ", 3}, "11" : {" 10 ": 8," 7 ": 2}," 12 ": {" 13" : 2, "10" : 6, "6" : 4}, "13" : {" 12 ": 2," 9 ": 9}}; var INF = 9999; function dijkstra(graph, start, end){ var v_arr = []; Var dis = {}; Var path = {} // record path for(var key in graph){dis[key] = INF; path[key] = start; } dis[start] = 0; var min_v = start; while(true){ v_arr.push(min_v); Var v_link = graph[min_v]; If (dis[min_v] + v_link[key] < dis[key]){dis[key] = if(dis[min_v] + v_link[key]){dis[key] = dis[min_v] + v_link[key]; path[key] = min_v; Var min_dis = INF; var min_dis = INF; var min_dis = INF; for(var key in graph){ if(v_arr.indexOf(key) >= 0){ continue; } if(dis[key] < min_dis){ min_dis = dis[key]; min_v = key; } } if(min_dis == INF){ break; } // Output the shortest path var link_path = []; var tmp_v = path[end]; link_path.push(end); while(tmp_v){ link_path.push(tmp_v); tmp_v = path[tmp_v]; if(tmp_v === start){ link_path.push(start); break; } } console.log(link_path); }; dijkstra(graph_dict, "1", "13");Copy the code