Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities.

A graph is a data structure consisting of a collection of nodes with edges. A graph can be oriented or unoriented. Diagrams have the following basic elements:

• Node, the Node
• Edge: Edge
• | V | : the total number of vertices in the graph
• | E | : the total number of connections in the graph

Implement a directed Graph class:

``````class Graph{
constructor() {
// Use map to describe vertex relationships in a graph
this.AdjList = new Map()}}Copy the code``````

Create a graph by creating a node:

``````let graph = new Graph()
Copy the code``````

``````addVertex(vertex) {
} else {
throw new Error('This vertex already exists! ')}}Copy the code``````

A, B, C, D all correspond to an array:

``'A'- > []'B'- > []'C'- > []'D'- > []Copy the code``

The array will be used to store edges, and the following relationship is expected:

``````'A'- > ['B'.'C'.'D']
'B'- > []'C'- > ['B']
'D'- > ['C']
Copy the code``````

``````addEdge(vertex, node) {
if(! arr.includes(node)) { arr.push(node) } }else {

## Print figure print

``````print() {
// Use for of to iterate over and print this.adjList
for (let [key, value] of this.AdjList) {
console.log(key, value)
}
}
Copy the code``````

``````createVisitedObject() {
let map = {}
for (let key of this.AdjList.keys()) {
arr[key] = false
}
return map
}
bfs (initialNode) {
// Create a map of the visited nodes
let visited = this.createVisitedObject()
// Simulate a queue
let queue = []
// The first node is accessed
visited[initialNode] = true
// The first node is queued
queue.push(initialNode)
while (queue.length) {
let current = queue.shift()
console.log(current)
// Get other node relationships for this node
for (let elem of arr) {
// If the current node is not accessed
if(! visited[elem]) { visited[elem] =true
queue.push(elem)
}
}
}
}
Copy the code``````

BFS- Search algorithm with queue implementation, implementation steps:

1. The start node acts as the start and initializes an empty object — visited;
2. Initialize an empty array that emulates a queue.
3. Mark the start node as visited;
4. Put the start node into the queue;
5. Loop until the queue is empty.

## Depth-first DFS

``````createVisitedObject() {
let map = {}
for (let key of this.AdjList.keys()) {
arr[key] = false
}
return map
}

Depth-first algorithm
dfs(initialNode) {
let visited = this.createVisitedObject()
this.dfsHelper(initialNode, visited)
}

dfsHelper(node, visited) {
visited[node] = true
console.log(node)
// Call this.dfshelper to traverse the node
for (let elem of arr) {
if(! visited[elem]) {this.dfsHelper(elem, visited)
}
}
}
Copy the code``````

DFS- Search algorithm using recursion to achieve the steps:

1. The start node is used as the start node to create access objects.
2. Call an auxiliary function recursively to the start node.