1. What is a graph

A graph is an abstract model of the structure of a network, a set of nodes linked by edges.

Any social network, such as Facebook, Twitter, and Google+, can be represented by a graph, and a graph can represent any binary relationship, such as roads, flights, etc

The diagram below:

1.1 Some terminology for diagrams

The mathematical and technical concepts of graphs

A graph G = (V, E) consists of the following elements.

V: a set of vertices E: a set of edges connecting vertices in V

The diagram below:

Vertices joined together by an edge are called adjacent vertices. For example, A and B are neighbors, A and D are neighbors, A and C are neighbors, and A and E are not neighbors.

The degree of a vertex is the number of adjacent vertices. For example, A is connected to three other vertices, so the degree of A is 3; E is connected to the other two vertices, so E has a degree of 2.

Paths are vertices V1v_1v1, v2V_2v2… , a continuous sequence of vkv_kvk, where viv_ivi and vi+1v_{I +1}vi+1 are adjacent. The diagram above, for example, contains paths ABEI and ACDG.

Simple paths require that there be no duplicate vertices. For example, ADG is a simple path. Except for the last vertex (because it is the same vertex as the first), the ring is also A simple path, such as ADCA (the last vertex returns to A).

A graph is acyclic if there are no rings in it. A graph is connected if there are paths between every two vertices

1.2 Directed and undirected graphs

A graph can be undirected (edges have no direction) or directed (digraph)

A graph is strongly connected if there are paths between every two vertices in both directions. For example, C and D are strongly connected, while A and B are not strongly connected.

The graph can also be unweighted or weighted. As shown in the figure below, the edges of the weighted graph are given weights

2. Representation of graphs

2.1 Adjacency matrix

The most common implementation of graphs is adjacency matrices. Each node is associated with an integer that acts as an index to the array. We use a two-dimensional array to represent the connections between vertices. If the node whose index is I is adjacent to the node whose index is j, array[I][j] === 1; otherwise, array[I][j] === 0, as shown in the following figure

If a graph that is not strongly connected (sparse graph) is represented by an adjacency matrix, the matrix will have a lot of zeros, which means we waste computer storage to represent edges that don’t exist at all. For example, to find adjacent vertices of a given vertex, even if the vertex has only one adjacent vertex, we have to iterate over an entire row.

Another reason the adjacency matrix representation is not good enough is that the number of vertices in the graph can change, and two-dimensional arrays are less flexible

2.2 adjacency table

We can also use a dynamic data structure called an adjacency list to represent graphs. The adjacency list consists of a list of adjacent vertices for each vertex in the graph. There are several ways to represent this data structure. We can use lists (arrays), linked lists, or even hash tables or dictionaries to represent lists of adjacent vertices. The following diagram shows the adjacency list data structure.

Although an adjacency list is probably a better choice for most problems, both of these representations are useful and have different properties (for example, it is faster to use an adjacency matrix to find out whether vertices V and W are adjacent).

2.3 Association Matrix

Graphs can also be represented by an association matrix. In an association matrix, the rows of the matrix represent vertices and the columns represent edges. As shown in the figure below, a two-dimensional array is used to represent the connectivity between the two. If vertex V is the incident point of edge E, array[v][e] === 1; Otherwise, array[v][e] === 0.

The incidence matrix is usually used when there are more edges than vertices to save space and memory

3. Implement a Graph class

Adjacency list implementation

export default class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // Whether there is direction
    this.vertices = []; // Store the names of all vertices in the graph
    this.adjList = new Map(a);// Store the adjacency list. Key is the vertex and the list of adjacency vertices is the value
  }
  
  // Add a new vertex to the graph
  addVertex(v) {
    if (!this.vertices.includes(v)) {
      this.vertices.push(v); // Store the vertex array
      this.adjList.set(v, []); }}// Add edges between vertices
  addEdge(a, b) {
    // If the point does not exist, add it to the vertex list
    if (!this.adjList.get(a)) {
      this.addVertex(a);
    }
    if (!this.adjList.get(b)) {
      this.addVertex(b);
    }
    
    // Add (directed graph)
    this.adjList.get(a).push(b);
    // Undirected graph, add each other
    if (this.isDirected ! = =true) {
      this.adjList.get(b).push(a); }}// Returns the list of vertices
  getVertices() {
    return this.vertices;
  }
  
  // return the adjacency list
  getAdjList() {
    return this.adjList;
  }
  
  toString() {
    let s = ' ';
    for (let i = 0; i < this.vertices.length; i++) {
      s += `The ${this.vertices[i]}- > `;
      const neighbors = this.adjList.get(this.vertices[i]);
      for (let j = 0; j < neighbors.length; j++) {
        s += `${neighbors[j]} `;
      }
      s += '\n';
    }
    returns; }}Copy the code

Test code:

const graph = new Graph(); 
const myVertices = ['A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I'];
for (let i = 0; i < myVertices.length; i++) {
 graph.addVertex(myVertices[i]); 
} 
graph.addEdge('A'.'B');
Copy the code

4. Graph traversal

Breadth first search (BFS) and depth first search graph traversal can be used to find specific vertices or find paths between two vertices, check whether the graph is connected, check whether the graph contains rings, and so on

The idea of graph traversal is that you must track every node that is visited for the first time and keep track of which nodes have not been fully explored. For both graph traversal algorithms, it is necessary to specify the first vertex to be visited.

Fully exploring a vertex requires us to look at every edge of that vertex. For the unvisited vertices connected by each edge, mark them as found and add them to the list of vertices to be visited.

To ensure the efficiency of the algorithm, it is important to visit each vertex at most twice. Every edge and vertex in a connected graph is accessed

  • Depth-first search uses a stack, storing vertices on the stack. Vertices are explored along the path, and new adjacent vertices are accessed
  • Breadth-first searches use queues, where vertices are queued and the first vertices queued are explored first

We use three colors to represent vertex states:

White: indicates that the vertex has not been accessed. Grey: indicates that the vertex has been visited but not explored. Black: indicates that the vertex was visited and fully explored.

The code is as follows:

const Colors = { 
 WHITE: 0.GREY: 1.BLACK: 2 
};
Copy the code

All vertices are first marked as not accessed

const initializeColor = vertices= > { 
 const color = {}; 
 for (let i = 0; i < vertices.length; i++) { 
 color[vertices[i]] = Colors.WHITE; 
 } 
 return color; 
};
Copy the code

4.1 Breadth-first search

The breadth-first search algorithm traverses the graph starting with the first vertex specified, visiting all of its neighbors first, like one layer of the graph at a time.

Code template

def BFS(root) :
    visited = set()
    queue = [] 
    queue.append([root]) 

    while queue: 
        node = queue.pop() 
        visited.add(node)
        process(node) 
        nodes = generate_related_nodes(node) 
        queue.push(nodes)
    # other processing work
Copy the code

Binary tree sequence traversal

const bfs = (root) = > {
  let result = [], queue = [root]
  while (queue.length > 0) {
    let level = [], n = queue.length
    for (let i = 0; i < n; i++) {
      let node = queue.pop()
      level.push(node.val) 
      if (node.left) queue.unshift(node.left)
      if (node.right) queue.unshift(node.right)
    }
    result.push(level)
  }
  return result
};
Copy the code

Shimo. Im/docs/P8TqKH…

The steps are as follows:

  1. Create a queue Q.
  2. Label V as found (gray) and queue V to Q.
  3. If Q is not empty, run the following steps:
  4. Dequeue u from Q;
  5. Marked U is found (gray);
  6. Queue all unvisited adjacent points of u (white);
  7. Marked U is explored (black).
export const breadthFirstSearch = (graph, startVertex, callback) = > {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  // Mark all vertices white
  const color = initializeColor(vertices);
  const queue = new Queue();
  // Add vertices to the team
  queue.enqueue(startVertex);

  while(! queue.isEmpty()) {const u = queue.dequeue();
    // Get the adjacency list of all its neighbors
    const neighbors = adjList.get(u);
    // Label the vertex gray
    color[u] = Colors.GREY;
    // Iterate over values in the adjacency list
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i];
      // If the point has not been visited, gray it out
      if (color[w] === Colors.WHITE) {
        color[w] = Colors.GREY;
        // Enqueue the pointqueue.enqueue(w); }}/ / the black
    color[u] = Colors.BLACK;
    if(callback) { callback(u); }}};Copy the code

Use BFS to find shortest paths

Given a graph G and source vertex V, find the shortest path distance (in number of edges) between each vertex u and v.

const BFS = (graph, startVertex) = > {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  const queue = new Queue();
  // Store distance
  const distances = {};
  / / back before
  const predecessors = {};
  queue.enqueue(startVertex);
  / / initialization
  for (let i = 0; i < vertices.length; i++) {
    distances[vertices[i]] = 0;
    predecessors[vertices[i]] = null;
  }
  while(! queue.isEmpty()) {const u = queue.dequeue();
    const neighbors = adjList.get(u);
    color[u] = Colors.GREY;
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i];
      if (color[w] === Colors.WHITE) {
        color[w] = Colors.GREY;
        // 距离+1
        distances[w] = distances[u] + 1;
        // If w is found adjacent to vertex u, set the value of w to u
        predecessors[w] = u;
        queue.enqueue(w);
      }
    }
    color[u] = Colors.BLACK;
  }
  return {
    distances,
    predecessors
  };
};
Copy the code

Note: Breadth-first search is not appropriate if you want to calculate the shortest path in A weighted graph (for example, the shortest path between city A and city B — the algorithm used in GPS and Google Maps).

Dijkstra algorithm solves the problem of single source shortest path. Bellman-ford algorithm solves the single source shortest path problem with negative edge weights. A* search algorithm solves the problem of finding the shortest path between only A pair of vertices and uses empirical rules to speed up the search process. Floyd-warshall algorithm solves the problem of finding the shortest path between all vertex pairs

4.2 Depth-first Search

A depth-first search algorithm will traverse the graph from the first specified vertex, follow the path until the last vertex of the path is visited, and then backtrack and explore the next path

Code template

visited = set(a)def dfs(node, visited) :
    if node in visited: # terminator
        # already visited
        return
    visited.add(node)
    # process current node here..for next_node in node.children():
        if next_node not in visited:
            dfs(next_node, visited)
Copy the code
def DFS(self, root) : 
    if tree.root is None: 
        return [] 
    visited, stack = [], [root]
    while stack: 
        node = stack.pop() 
        visited.add(node)
        process (node) 
        Generate the relevant nodes
        nodes = generate_related_nodes(node) 
        stack.push(nodes) 
    # other processing work.Copy the code
const visited = new Set(a)const dfs = node= > {
  if (visited.has(node)) return
  visited.add(node)
  dfs(node.left)
  dfs(node.right)
}
Copy the code

Shimo. Im/docs/ddgwCc…

Depth-first search algorithms do not require a source vertex. In depth-first search algorithm, if vertex V in the graph is not accessed, the vertex V is accessed.

  1. V is found (gray);
  2. For all unvisited (white) adjacent points w of V, vertex W is visited;
  3. Mark V as explored (black).
const depthFirstSearchVisit = (u, color, adjList, callback) = > {
  // The color is gray
  color[u] = Colors.GREY;
  if (callback) {
    callback(u);
  }
  // Get a list of all the neighbors of vertex u
  const neighbors = adjList.get(u);
  for (let i = 0; i < neighbors.length; i++) {
    const w = neighbors[i];
    // If not, recursively access
    if (color[w] === Colors.WHITE) {
      depthFirstSearchVisit(w, color, adjList, callback);
    }
  }
  color[u] = Colors.BLACK;
};

const depthFirstSearch = (graph, callback) = > {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);

  for (let i = 0; i < vertices.length; i++) {
    if(color[vertices[i]] === Colors.WHITE) { depthFirstSearchVisit(vertices[i], color, adjList, callback); }}};Copy the code

The exploration process is shown as follows:

Explore depth-first algorithms

For a given graph G, we want a depth-first search algorithm to traverse all nodes of graph G, building a “forest” (a set of trees with roots) as well as a set of source vertices (roots), and output two arrays: discovery time and exploration completion time. We can modify the depthFirstSearch function to return some information

  • The discovery time of vertex U d[u];
  • When vertex U is marked black, the exploration time of u is f[u].
  • The retroactive point p[u] of vertex U.

Improved implementation of DFS methods

const DFSVisit = (u, color, d, f, p, time, adjList) = > {
  // console.log('discovered ' + u);
  color[u] = Colors.GREY;
  // When a vertex is first discovered, we track its discovery time
  d[u] = ++time.count;
  const neighbors = adjList.get(u);
  for (let i = 0; i < neighbors.length; i++) {
    const w = neighbors[i];
    if (color[w] === Colors.WHITE) {
      // When it is found by referring to the edge of vertex u, we trace its back point
      p[w] = u;
      DFSVisit(w, color, d, f, p, time, adjList);
    }
  }
  color[u] = Colors.BLACK;
  // When the vertex is fully explored, we track its completion time
  f[u] = ++time.count;
  // console.log('explored ' + u);
};

export const DFS = graph= > {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  const d = {};
  const f = {};
  const p = {};
  // Declare a variable to track the time of discovery and completion of exploration
  const time = { count: 0 };
  // We declare arrays D, f, and p to initialize these arrays for each vertex of the graph
  for (let i = 0; i < vertices.length; i++) {
    f[vertices[i]] = 0;
    d[vertices[i]] = 0;
    p[vertices[i]] = null;
  }
  for (let i = 0; i < vertices.length; i++) {
    if(color[vertices[i]] === Colors.WHITE) { DFSVisit(vertices[i], color, d, f, p, time, adjList); }}return {
    discovery: d,
    finished: f,
    predecessors: p
  };
};
Copy the code
  • Time (time) the scope of a variable’s value can only be in figure one or two times the number of vertices (2 | V |);
  • For all vertices u, d[u]

Under these two assumptions, we have the following rule. 1 <= d [u] < f [u] <= 2|V|

If we run the new depth-first search over the same graph, we get the following discovery/completion times for each vertex in the graph

Topological sort – use depth-first search

Given the figure below, assume that each vertex is a task we need to perform

This is a directed graph, meaning that tasks are executed sequentially. For example, task F cannot be executed before task A. Notice that this graph has no rings, which means it’s an acyclic graph. Therefore, we can say that the graph is a directed acyclic graph

When we need to arrange the execution order of tasks or steps, this is called topological sorting (also known as topsort or toposort). In everyday life, this problem arises in different situations. For example, when we start a computer science course, we have to complete a few pieces of knowledge in order to learn something (you can’t take Algorithms I before algorithms II).

Topological sort applies only to DAGs. So how do you use depth-first search to achieve topological sorting? Let’s perform a depth-first search on the diagram at the beginning of this section

graph = new Graph(true); / / directed graph
myVertices = ['A'.'B'.'C'.'D'.'E'.'F']; 
for (i = 0; i < myVertices.length; i++) { 
 graph.addVertex(myVertices[i]); 
} 
graph.addEdge('A'.'C'); 
graph.addEdge('A'.'D'); 
graph.addEdge('B'.'D'); 
graph.addEdge('B'.'E'); 
graph.addEdge('C'.'F'); 
graph.addEdge('F'.'E'); 
const result = DFS(graph);
Copy the code

This code creates the graph, adds edges, performs an improved version of the depth-first search algorithm, and saves the result to the Result variable. The figure below shows the discovery and completion time of the graph after the depth-first search algorithm is executed

All you need to do now is sort the completion time array in reverse order, resulting in a topological sort of the graph, as shown below.

const fTimes = result.finished; 
s = ' '; 
for (let count = 0; count < myVertices.length; count++) { 
 let max = 0; 
 let maxName = null; 
 for (i = 0; i < myVertices.length; i++) { 
 if (fTimes[myVertices[i]] > max) { 
 max = fTimes[myVertices[i]]; 
 maxName = myVertices[i]; 
 } 
 } 
 s += The '-' + maxName; 
 delete fTimes[maxName]; 
} 
console.log(s); 
Copy the code

After executing the above code, we get the following output. B – A – D – C – F – E Note that the previous topological ordering result is only one of many possibilities. If we modify the algorithm a little bit, we get a different result. The result below, for example, is one of many other possibilities. A-b-c-d-f-e is also an acceptable result

4.3 Differences between BFS and DFS

  1. DFS can be thought of as backtracking
  2. BFS is used to find the shortest path. However, the space complexity is greater than DFS

5. Shortest path algorithm

5.1 Dijkstra algorithm

Dijkstra is a greedy algorithm that computes the shortest path from a single source to all other sources

The adjacency matrix of the figure above is as follows:

var graph = [
    [0.2.4.0.0.0], 
    [0.0.1.4.2.0], 
    [0.0.0.0.3.0], 
    [0.0.0.0.0.2], 
    [0.0.0.3.0.2], 
    [0.0.0.0.0.0]]Copy the code
const INF = Number.MAX_SAFE_INTEGER;
const minDistance = (dist, visited) = > {
  let min = INF;
  let minIndex = -1;
  for (let v = 0; v < dist.length; v++) {
    if (visited[v] === false&& dist[v] <= min) { min = dist[v]; minIndex = v; }}return minIndex;
};

const dijkstra = (graph, src) = > {
  const dist = [];
  const visited = [];
  const { length } = graph;
  for (let i = 0; i < length; i++) { // Start all distances as infinite
    dist[i] = INF;
    visited[i] = false;
  }
  dist[src] = 0; // Set the distance between the source vertex and itself to 0
  for (let i = 0; i < length - 1; i++) { // Find the shortest path to the remaining vertices
    const u = minDistance(dist, visited); // Select the nearest vertex from the unprocessed vertices
    visited[u] = true; // Label the selected vertex as visited to avoid double counting
    for (let v = 0; v < length; v++) {
      if(! visited[v] && graph[u][v] ! = =0&& dist[u] ! == INF && dist[u] + graph[u][v] < dist[v]) {// If a shorter path is found, the shortest path value is updateddist[v] = dist[u] + graph[u][v]; }}}return dist; // After processing all vertices, return the result of the shortest path from the source vertex (SRC) to the other vertices in the graph
};
Copy the code

5.2 Floyd – Warshall algorithm

Floyd-warshall algorithm is a dynamic programming algorithm that computs all shortest paths in a graph.

const floydWarshall = graph= > {
  const dist = [];
  const { length } = graph;
  for (let i = 0; i < length; i++) { // Initialize the distance array to the weights between each vertex
    dist[i] = [];
    for (let j = 0; j < length; j++) {
      if (i === j) {
        dist[i][j] = 0; // The distance between the vertex and itself is 0
      } else if (!isFinite(graph[i][j])) {
        dist[i][j] = Infinity; // If two vertices have no edges between them, they are Infinity
      } else{ dist[i][j] = graph[i][j]; }}}for (let k = 0; k < length; k++) { // use vertices 0 to k as intermediate points
    for (let i = 0; i < length; i++) {
      for (let j = 0; j < length; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) { The shortest path from I to j goes through k
          dist[i][j] = dist[i][k] + dist[k][j]; // If a new value of the shortest path is found, we use it and store it}}}}return dist;
};
Copy the code

6. Minimum spanning tree

Minimum spanning tree (MST) problem is a common problem in network design. Imagine that your company has several offices. What is the best way to save money by connecting office telephone lines with each other at the lowest cost?

This also applies to the island bridge problem. Imagine you want to build a bridge between n islands, and you want to connect them all to each other at the lowest cost

var graph = [
    [0.2.4.0.0.0], 
    [2.0.2.4.2.0], 
    [4.2.0.0.3.0], 
    [0.4.0.0.3.2], 
    [0.2.3.3.0.2], 
    [0.0.0.2.2.0]].Copy the code

6.1 Prim algorithm

Prim algorithm is a greedy algorithm for MST problem of weighted undirected connected graph. It can find a subset of edges such that the tree contains all the vertices in the graph, and the sum of edge weights is minimum

const INF = Number.MAX_SAFE_INTEGER;
const minKey = (graph, key, visited) = > {
  let min = INF;
  let minIndex = 0;
  for (let v = 0; v < graph.length; v++) {
    if (visited[v] === false&& key[v] < min) { min = key[v]; minIndex = v; }}return minIndex;
};
export const prim = graph= > {
  const parent = [];
  const key = [];
  const visited = [];
  const { length } = graph;
  for (let i = 0; i < length; i++) { // initialize all vertices to be infinite
    key[i] = INF;
    visited[i] = false;
  }
  // Select the first key as the first vertex, and since the first vertex is always the root of the MST, parent[0] = -1
  key[0] = 0;
  parent[0] = -1;
  for (let i = 0; i < length - 1; i++) { // Find MST for all vertices
     // Select the vertex with the lowest key from the unprocessed vertex set
    const u = minKey(graph, key, visited);
    // Label the selected vertex as visited to avoid double counting
    visited[u] = true;
    for (let v = 0; v < length; v++) {
      if(graph[u][v] && ! visited[v] && graph[u][v] < key[v]) { parent[v] = u;// Save the MST path if you get a smaller weight
        // Update its weightkey[v] = graph[u][v]; }}}return parent;
};
Copy the code

6.2 Kruskal algorithm

const INF = Number.MAX_SAFE_INTEGER;
const find = (i, parent) = > {
  while (parent[i]) {
    i = parent[i]; // eslint-disable-line prefer-destructuring
  }
  return i;
};
const union = (i, j, parent) = > {
  if(i ! == j) { parent[j] = i;return true;
  }
  return false;
};
const initializeCost = graph= > {
  const cost = [];
  const { length } = graph;
  for (let i = 0; i < length; i++) {
    cost[i] = [];
    for (let j = 0; j < length; j++) {
      if (graph[i][j] === 0) {
        cost[i][j] = INF;
      } else{ cost[i][j] = graph[i][j]; }}}return cost;
};
export const kruskal = graph= > {
  const { length } = graph;
  const parent = [];
  let ne = 0;
  let a;
  let b;
  let u;
  let v;
  // Copy the value of the adjacency matrix to the cost array for easy modification and can retain the original value
  const cost = initializeCost(graph);
  while (ne < length - 1) { // The number of edges in MST is less than the total number of vertices minus 1
    for (let i = 0, min = INF; i < length; i++) { // Find the edge with the lowest weight
      for (let j = 0; j < length; j++) {
        if(cost[i][j] < min) { min = cost[i][j]; a = u = i; b = v = j; }}}// Check if the edge already exists in the MST to avoid loops
    u = find(u, parent);
    v = find(v, parent);
    if (union(u, v, parent)) { // If u and v are different edges, add them to MST
      ne++;
    }
    cost[a][b] = cost[b][a] = INF; // Remove the edges from the list to avoid double-counting
  }
  return parent;
};
Copy the code

7. Common depth and breadth first search test questions

1.easy

2.medium

1.Sequential traversal of binary trees

Difficulty: Medium

The sequence traversal BFS of binary tree

2.Minimum genetic change

Difficulty: Medium

Solution: Minimal genetic variation BFS

3.Parentheses generates

Difficulty: Medium

Solution: Parenthesis generation (BFS+DFS)

4.Look for the maximum value in each tree row

Difficulty: Medium

Find the maximum value in each tree row (BFS)

5.The number of islands

Difficulty: Medium

Number of islands DFS

General solution of island problem, DFS ergodic framework

6.minesweeper

Difficulty: Medium

Solution: Minesweeper (DFS)

7.Pacific Atlantic current problems

Difficulty: Medium

Pacific Atlantic Flow problem (DFS)

8.Cloning figure

Difficulty: Medium

Clone diagram (DFS+BFS)

9.Open the turntable lock

Difficulty: Medium

Open the turntable lock (BFS)

3.hard

9.randomly

Difficulty: difficulty

The word solitaire BFS