The definition of “graph class” in “you should know a little bit about Javascript algorithm series” and the depth-first and breadth-first search algorithms

  javascript

Figure
Github direct addresshttps://github.com/fanshyiis/ …

In computer science, a graph is a set of vertices that are paired (connected) by a series of edges. Vertices are represented by circles, and edges are the connecting lines between these circles. Vertices are connected by edges.

Note: Vertices are sometimes called nodes or intersections, while edges are sometimes called links.

A graph can represent a social network, each person is a vertex, and people who know each other are connected by edges.

In theory, a graph is just a bunch of vertices and edge objects, but how can it be described in code?
There are two main methods: adjacency list and adjacency matrix.

Adjacent listIn the adjacency list implementation, each vertex stores a list of edges starting from it. For example, if vertex A has one edge to B, C, and D, then there will be 3 edges in A’s list

clipboard.png

The adjacency list only describes the edges pointing to the outside. A has an edge to b, but b has no edge to a, so a does not appear in b’s adjacency list. Finding an edge or weight between two vertices is time consuming because it traverses the adjacency list until it is found.

Adjacency matrixIn the implementation of the adjacency matrix, the vertices are represented by rows and columns, and the corresponding elements of the matrix determined by the two vertices represent whether the two vertices are connected, and if so, the value of connection represents the weight of the connected edges. For example, if there is an edge with a weight of 5.6 from vertex A to vertex B, then the element value at the position of row A and column B in the matrix should be 5.6:

clipboard.png

Adding vertices to this graph is very expensive, because the new matrix results must be recreated according to the new rows/columns, and then the existing data must be copied to the new matrix.
So which one to use? Most of the time, it is correct to select the adjacency list. The following is a more detailed comparison of the two implementation methods.
Suppose V represents the number of vertices in the graph and E represents the number of edges.

clipboard.png

“Check adjacency” refers to trying to determine whether a given vertex is a neighbor of another vertex. The time complexity of checking adjacency in the adjacency list is O(V), because the worst case is that one vertex is connected to each vertex.
In the case of sparse graphs, each vertex will only be connected to a few vertices. In this case, the neighbor list is the best choice. If this graph is relatively dense and each vertex is connected to most other vertices, then the adjacent matrix is more appropriate.


After understanding the basic definition of graphs, let’s look at how to use es6′ s class idea to implement graph classes.


First, we define two auxiliary classes

class Dictionary {
 constructor () {
 this.items = {}
 }
 
 has (key) {
 return key in this.items
 }
 
 set (key, val) {
 this.items[key] = val
 }
 
 delete (key) {
 if (this.has(key)) {
 delete this.items[key]
 return true
 } else {
 return false
 }
 }
 
 get (key) {
 return this.has(key)?  this.items[key] : undefined
 }
 
 values () {
 let values = []
 for (let k in this.items) {
 if (this.has(k)) {
 values.push(this.items[k])
 }
 }
 return values
 }
 }
 
 class Queue {
 constructor () {
 this.items = []
 }
 
 enqueue (element) {
 this.items.push(element)
 }
 
 dequeue () {
 return this.items.shift()
 }
 
 isEmpty() {
 return this.items.length === 0
 }
 }

DictionaryDictionary classes to assist in storing key-value pairs
QueueQueue class to store queues

//define class Graph
 class Graph {
 constructor () {
 this.vertices = []
 this.adjList = new Dictionary()
 }
 }

Define the Graph class and initialize the fields in the constructor
verticesStorage point information
adjListStores link relationships between vertices

addVertex (v) {
 this.vertices.push(v)
 this.adjList.set(v, [])
 }
 
 addEdge (v, w) {
 this.adjList.get(v).push(w)
 }

addVertexThe method of adding vertices is stored in the array vertices and the values in the adjList dictionary are initialized.
addEdgeAdd a one-way edge to receive two values and add a relationship from the first vertex to the second in the adjacency dictionary

By the time this basic class is finished, we can test it by testing the code.

et graph = new Graph()
 let mv = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
 mv.map(val => {
 graph.addVertex(val)
 })
 graph.addEdge('A', 'B')
 graph.addEdge('A', 'C')
 graph.addEdge('A', 'D')
 graph.addEdge('C', 'D')
 graph.addEdge('C', 'G')
 graph.addEdge('D', 'G')
 graph.addEdge('D', 'H')
 graph.addEdge('B', 'E')
 graph.addEdge('B', 'F')
 graph.addEdge('E', 'I')

The resulting graph

clipboard.png

Let’s define a function to print a diagram

toString () {
 let s = ''
 for (let i = 0;   i < this.vertices.length;  i++) {
 s += this.vertices[i] + '->'
 let neighbors = this.adjList.get(this.vertices[i])
 for (let j = 0;   j < neighbors.length;  j++) {
 s += neighbors[j] + ' '
 }
 s += '\n'
 }
 return s
 }

Js

Get results

A->B C D
 B->E F
 C->D G
 D->G H
 E->I
 F->
 G->

Good to this basically completed the structure of the class, the following graph traversal

Breadth First-Data Structure Queue

Code first

BFS (v, callback) {
 let color = this.initializeColor(),
 queue = new Queue()
 queue.enqueue(v)
 
 while (!  queue.isEmpty()) {
 let u = queue.dequeue(),
 neighbors = this.adjList.get(u)
 color[u] = 'grey'
 neighbors.map(val => {
 if (color[val] === 'white') {
 color[val] = 'grey'
 queue.enqueue(val)
 }
 })
 color[u] = 'black'
 if (callback) {
 callback(u)
 }
 }
 }

The basic idea is as follows
1. Initialize the color of each vertex (white-not accessed; Gray-Found; Black-already explored)
2. Initialize a queue
3. First of all, the team is listed as vertex V.
4. If the queue is not empty, take the first queue for exploration.
5. In the process of exploration, all adjacent vertices of the current vertex are obtained and the queue is pushed forward
6. After completing 5, the mark is currently black

Figure example
A exploration team included in B-C-D
Complete exploration a
Exit b, explore b queue, re-enter E-F current CDEF
Complete exploration b
Exit c exploration queue re-enters g current DEFG
. . .

Until all the vertices are explored

clipboard.png

Depth First-Data Structure Stack

Code first

DFS (callback) {
 let color = this.initializeColor()
 this.vertices.map(val => {
 if (color[val] === 'white') {
 this.dfsVisit(val, color, callback)
 }
 })
 }
 
 dfsVisit (u, color, callback) {
 color[u] = 'grey'
 if (callback) {
 callback(u)
 }
 let neighbors = this.adjList.get(u)
 neighbors.map(val => {
 if (color[val] === 'white') {
 this.dfsVisit(val, color, callback)
 }
 })
 color[u] = 'black'
 }

The principle of depth first takes stack as data structure

The basic idea is as follows
1. Initialize the color of each vertex (white-not accessed; Gray-Found; Black-already explored)
2. Traversing vertices and exploring dfsVisit function
3. Give priority to the latest exploration while conducting in-depth exploration, and mark the completion of exploration after completion.

The basic steps are as follows
Explore a
BCD found
Explore b
Found EF
Explore e
Discovery i
Exploration I, completion mark I is exploration
Go back to the previous branch traversal and then perform exploration f
Complete
Mark f for exploration
. . .
Until returning to vertex a

Complete exploration

There are also PLus version of the depth and breadth-first algorithm, the specific code is provided

/*
* @Author: koala_cpx
* @Date:   2019-01-24 10:48:01
* @Last Modified by:   koala_cpx
* @Last Modified time: 2019-01-24 10:56:33
*/
class Dictionary {
  constructor () {
    this.items = {}
  }

  has (key) {
    return key in this.items
  }

  set (key, val) {
    this.items[key] = val
  }

  delete (key) {
    if (this.has(key)) {
      delete this.items[key]
      return true
    } else {
      return false
    }
  }

  get (key) {
    return this.has(key)? this.items[key] : undefined
  }

  values () {
    let values = []
    for (let k in this.items) {
      if (this.has(k)) {
        values.push(this.items[k])
      }
    }
    return values
  }
}

class Queue {
  constructor () {
    this.items = []
  }

  enqueue (element) {
    this.items.push(element)
  }

  dequeue () {
    return this.items.shift()
  }

  isEmpty() {
    return this.items.length === 0
  }
}

class Graph {
  constructor () {
    this.vertices = []
    this.adjList = new Dictionary()
    this.time = 0
  }

  addVertex (v) {
    this.vertices.push(v)
    this.adjList.set(v, [])
  }

  addEdge (v, w) {
    this.adjList.get(v).push(w)
    // this.adjList.get(w).push(v)
  }

  BFS (v, callback) {
    let color = this.initializeColor(),
        queue = new Queue()
    queue.enqueue(v)

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      color[u] = 'grey'
      neighbors.map(val => {
        if (color[val] === 'white') {
          color[val] = 'grey'
          queue.enqueue(val)
        }
      })
      color[u] = 'black'
      if (callback) {
        callback(u)
      }
    }
  }

  BFSPlus (v) {
    let color = this.initializeColor(),
        queue = new Queue(),
        d = [],
        pred = []

    queue.enqueue(v)
    this.vertices.map(val => {
      d[val] = 0
      pred[val] = null
    })

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      
      color[u] = 'grey'
      neighbors.map(val => {
        if (color[val] === 'white') {
          color[val] = 'grey'
          d[val] = d[u] + 1
          pred[val] = u
          queue.enqueue(val)
        }
      })
      color[u] = 'black'
    }

    return {
      distances: d,
      predecessors: pred
    }
  }

  DFS (callback) {
    let color = this.initializeColor()
    this.vertices.map(val => {
      if (color[val] === 'white') {
        this.dfsVisit(val, color, callback)
      }
    })
  }

  DFSPlus () {
    let color = this.initializeColor(),
        d = [],
        f = [],
        p = []

    this.time = 0
    this.vertices.map(val => {
      f[val] = 0
      d[val] = 0
      p[val] = null
    })

    this.vertices.map(val => {
      if (color[val] === 'white') {
        this.dfsPlusVisit(val, color, d, f, p)
      }
    })

    return {
      discovery: d,
      finished: f,
      predecessors: p
    }
  }

  dfsPlusVisit (u, color, d, f, p) {
    console.log('discovery' + u)
    color[u] = 'grey'
    d[u] = ++this.time
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === 'white') {
        p[val] = u
        this.dfsPlusVisit(val, color, d, f, p)
      }
    })
    color[u] = 'black'
    f[u] = ++this.time
    console.log('explored' + u)
  }

  dfsVisit (u, color, callback) {
    color[u] = 'grey'
    if (callback) {
      callback(u)
    }
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === 'white') {
        this.dfsVisit(val, color, callback)
      }
    })
    color[u] = 'black'
  }

  outPut(obj) {
    let fromVertex = this.vertices[0],
        { predecessors } = obj
    this.vertices.map(val => {
      let path = new Array()
      for (var v = val; v !== fromVertex; v = predecessors[v]) {
        path.push(v)
      }
      path.push(fromVertex)
      let s = path.pop()
      while (path.length !== 0) {
        s += ' -- ' + path.pop()
      }
      console.log(s)
    })
  }

  initializeColor () {
    let color = []
    this.vertices.map(val => {
      color[val] = 'white'
    })
    return color
  }

  toString () {
    let s = ''
    for (let i = 0; i < this.vertices.length; i++) {
      s += this.vertices[i] + '->'
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        s += neighbors[j] + ' '
      }
      s += '\n'
    }
    return s
  }
}

let a = new Dictionary()
a.set('ss', 1111)
a.set('s1', 1111)
a.set('s2', 1112)
a.set('s3', 1114)

a.delete('s2')
console.log(a.has('s3'))

console.log(a.values())

let graph = new Graph()
let mv = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
mv.map(val => {
  graph.addVertex(val)
})
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('E', 'I')

console.log(graph.toString())

function print(val) {
  console.log('vis' + val)
}

graph.BFS('A', print)
console.log(graph.BFSPlus("A"))
graph.outPut(graph.BFSPlus("A"))
graph.DFS(print)
console.log(graph.DFSPlus())

let graph2 = new Graph()
let mv2 = ['A', 'B', 'C', 'D', 'E', 'F']
mv2.map(val => {
  graph2.addVertex(val)
})
graph2.addEdge('A', 'C')
graph2.addEdge('A', 'D')
graph2.addEdge('B', 'D')
graph2.addEdge('B', 'E')
graph2.addEdge('C', 'F')
graph2.addEdge('F', 'E')

let r = graph2.DFSPlus()
console.log(r)

Github direct addresshttps://github.com/fanshyiis/ …