This is the seventh day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

The previous chapter introduced another form of tree binary tree, and said the recursive version of the first in the order of traversal.

This chapter takes a look at this data structure.

figure

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

  • Graphs can represent any binary relationship such as roads, flights……

  • There are no graphs in JS, but you can build them with Objects and arrays.

  • Representation of graphs: adjacency matrix, adjacency list, association matrix……

A representation of a graph

The diagram below:

Adjacency matrix

The adjacency matrix can be expressed as follows:

Every two intersection points of one, means that the two points are connected.

Adjacency list

The adjacency list can be expressed as follows:

Each point represents the corresponding key, and each key contains the point at which they are connected.

Common operations for diagrams

  • Depth-first traversal: Search branches of the graph as deeply as possible.

  • Breadth-first traversal: The node closest to the root is accessed first.

The figure below

The code is shown as follows:

const graph = {
    0: [1.2].1: [2].2: [0.3].3: [3]}Copy the code

Depth first traversal

  • Accessing the root node
  • For the root node Do a depth-first traversal one by one.

Depth-first traversal is done with the following code:

const visited = new Set()
const dfs = (node) => {
    console.log(node);
    visited.add(node)
    graph[node].forEach(c => {
        if(! visited.has(c)) {
            dfs(c)
        }
    })
}
dfs(2)
// 2 0 1 3

Copy the code

Breadth first traversal

  • Create a new queue and enqueue the root node.

  • Take the team leader out of line and visit.

  • Join the queue of adjacent nodes that have not been visited.

  • Repeat steps 2 and 3 until the queue is empty.

Breadth-first traversal is done with the following code:

const visited = new Set()
const q = [2]
visited.add(2)
while (q.length) {
    const node = q.shift()
    console.log(node);
    graph[node].forEach(c => {
        if(! visited.has(c)) {
            q.push(c)
            visited.add(c)
        }
    })
}

// 2 0 3 1
Copy the code

End~~~