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()
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')
Copy the code

AddVertex addVertex

addVertex(vertex) {
    if(!this.AdjList.has(vertex)) {
        this.AdjList.set(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

Add edge addEdge

addEdge(vertex, node) {
    if(this.AdjList.has(vertex)) {
        if(this.AdjList.has(node)) {
            let arr = this.AdjList.get(vertex)
            if(! arr.includes(node)) { arr.push(node) } }else {
            throw new Error('Cannot add')}}else {
        throw new Error('Please add vertices first${vertex}`)}}Copy the code

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

Breadth-first traversal of BFS

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
        let arr = this.AdjList.get(current)
        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)
    let arr = this.AdjList.get(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.

One last word

If this article is helpful to you, or inspired, help pay attention to it, your support is the biggest motivation I insist on writing, thank you for your support.