#### 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

Figure

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?

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 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: 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. “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 = []
}
}``````

Define the Graph class and initialize the fields in the constructor
verticesStorage point information

``````addVertex (v) {
this.vertices.push(v)
}

}``````

addVertexThe method of adding vertices is stored in the array vertices and the values in the adjList dictionary are initialized.

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 => {
})

The resulting graph 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] + '->'
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

Code first

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

while (!  queue.isEmpty()) {
let u = queue.dequeue(),
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 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)
}
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
*/
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.time = 0
}

this.vertices.push(v)
}

}

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

while (!queue.isEmpty()) {
let u = queue.dequeue(),
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(),

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
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)
}
neighbors.map(val => {
if (color[val] === 'white') {
this.dfsVisit(val, color, callback)
}
})
color[u] = 'black'
}

outPut(obj) {
let fromVertex = this.vertices,
{ 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] + '->'
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 => {
})

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 => {