This is the 10th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 Hello everyone, I am Xiao Cheng, a sophomore front-end enthusiast

📢 This article looks at graphs in data structures

📢 Thank you very much for reading

📢 May you be true to yourself and love life

💡 Knowledge points look first

  • What is a graph structure?
  • What are the application scenarios of graph structure?
  • What are the methods of graph structure?
  • How to implement a graph structure?
  • LeetCode of actual combat

📢 twitter

Graph structure is a structure that I think is very interesting. It can represent a very common scene in our life and also solve many problems. Let’s explore it together

What is graph structure?

Graph structure is an abstract model of network structure. It is a set of nodes connected by edges

At the same time, the graph can represent any binary relationship, such as road, flight…

So why is it possible to represent a binary relationship?

  • Because every edge in a graph is joined by two nodes, a graph can represent any binary relationship

In our daily life, wechat and other social software, our friend network can also be visualized as a graph structure, which can represent a variety of rich relationship structures

There is no graph structure in JS, we can build a graph structure from objects or arrays

So how do we represent these abstract graph structures, and we’re going to talk about 3 methods here

  • Adjacency matrix
  • Adjacency list
  • Incidence matrix

2. Terms related to graphs

A graph consists of G = (V,E), where V represents a set of vertices and E represents a set of edges connecting vertices in V

For example, in the following graph structure, key represents the vertex and value represents the node connected to the vertex

const graph = {
    0: [1.2].1: [2].2: [0.3].3: [3]};Copy the code
The term meaning
The vertices The basic unit of a graph, that is, the nodes in the graph
edge The relationships between vertices are called edges
Adjacent vertices Vertices joined together by an edge
The degree of The number of adjacent vertices that a vertex contains

How to understand these terms? Let’s explain it in terms of the graph structure

So again, let’s look at node A

  • ANodes andBAdjacent nodes,A 和 DIt’s adjacent,A 和 CIt’s adjacent,A 和 ENot adjacent, soANodes andB,C,DIs an adjacent node
  • Every node in the graph can exist as a vertex
  • AThe degree of the node is due toAIt’s connected to the other three nodes, soAThe degree of the node is zero3In the figure,DNodes and others4Theta is connected, so its degree is theta4
  • You can see in the pictureCDGIt forms a ring, so it’s also called a ring
  • A graph is connected if there is a path between every two vertices

Directed graph

The edges between nodes in the figure are unidirectional

Undirected graph

The edges between nodes in a graph are bidirectional, or have no direction, called an undirected graph

How to represent a graph?

There are many ways to represent a graph, there is no absolute method, you need to determine the type of graph according to the problem to be solved

1. Adjacency matrix

We can use A two-dimensional array to determine the connection between vertices. If A can connect to B, we set it to 1. If not, we set it to 0

Figure A is connected to node B, so the second column in the first row is 1, indicating that A is connected to node B

2. The adjacency list

Adjacency lists are used to represent a graph more visually and easily

It just tells you which vertex is connected to which vertex, very clearly

As shown in figure B, node B is connected to node C and node D, and node C is connected to node E, which is very convenient and recommended

4. Operation of graph

The following operations are based on this graph structure, which is represented by an adjacency list

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

1. Depth-first Traversal (DFS)

Search for as deep a branch of the graph as possible, similar to a pre-tree walk

  • Start by accessing the root node
  • The adjacent nodes of the root node that have not been visited are traversed depth-first one by one

Code implementation

// Record the nodes visited
const visited = new Set(a)Depth-first traversal
const dfs = (n) = > {
    console.log(n);
    visited.add(n)
    // Get all adjacent nodes
    graph[n].forEach(c= > {
        // If there is no access
        if(! visited.has(c)) { dfs(c) } }) }/ / the root node
dfs(2) 
Copy the code

Output result: 2 0 1 3

2. Breadth-first traversal (BFS)

The node closest to the root node is visited first, similar to a tree sequence traversal

Traversal method

  1. Create a new queue, enqueue the root node and access it
  2. Enqueue adjacent nodes that have not been visited by the opponent
  3. Repeat until the queue is empty

Code implementation

// width first traversal
const bfs = (n) = > {
    const visited = new Set(a); visited.add(n);const q = [n];
    while (q.length) {
        const n = q.shift();
        console.log(n);
        graph[n].forEach(c= > {
            if(! visited.has(c)) { q.push(c) visited.add(c); }}); }}Copy the code

Output result: 2 0 3 1

There are many similar to the shortest path, topological sorting, critical path and other problems, a little difficult, I will not discuss interested in their own research ~

What are the methods of graph structure?

According to the above introduction, we have a certain understanding of the graph structure, next we encapsulate a graph structure, first of all, to understand the method of the graph structure

methods meaning
addVertex(value) Adds a vertex to the graph
addEdge(a,b) Adds an edge between two points to the diagram
getVertices() Returns a list of vertices for the graph
toString() Output as a string

Six, handwriting to achieve undirected graph structure

1. Create Graph class

First we need to create a Graph constructor to hold the properties and methods in the Graph

Here we add two attributes, a vertices to hold vertices, and edgs to represent the adjacency list

class Graph {
    constructor() {
        this.vertices = [] // Save vertices
        this.edges = [] // Save edge, equivalent to adjacency list}}Copy the code

2. Implement addVertex method

Add this vertex, let’s check if we have this vertex in the picture, if we do, we won’t add it, if we don’t, we’ll add it to the list of vertices, and we’ll add it to the adjacency list to build edges

addVertex(value) {
    // If there is no vertex
    if(!this.vertices.includes(value)){
        this.vertices.push(value) // Add to the list of vertices
        this.edges[value] = []    // Add to the adjacency list}}Copy the code

3. Implement addEdge method

We through this method to establish the connection, the relationship between accepts two parameters, said the need to connect the two nodes, when the two nodes are present, and there is no connect, we further adjacency table modification operations, specific implementation is, connect the a to b in the array, b in a connection in the array

addEdge(a,b) {
    if(this.vertices.includes(a) && this.vertices.includes(b)) {
        if(!this.edges[a].includes(b)) {
            this.edges[a].push(b)
            this.edges[b].push(a)
        }
    }
}
Copy the code

4. Implement getVertices

We just return our array of vertices

getVertices() {
    return this.vertices
}
Copy the code

5. Implement toString

The key to implementing this approach is to clarify the relationship between each level

Using array to realize adjacency list will result in high time complexity of traversal. I think map or SET class can be used to realize adjacency list in the later stage

Implementation approach

  • Let’s go through the list of vertices
  • Finds the object corresponding to the list of vertices in the adjacency list
  • Concatenate string to achieve output
toString() {
    let s = "";
    // Iterate over the list of vertices in the graph
    for (let i = 0; i < this.vertices.length; i++) {
        // Use template strings for concatenation
        s += `The ${this.vertices[i]}- > `;
        // Get the array of adjacency lists corresponding to vertices
        const neighbors = this.edges[this.vertices[i]]
        // Iterates through the adjacency list array, deconstructing the numbers into strings
        for (let j = 0; j < neighbors.length; j++) {
            s += `${neighbors[j]} `;
        }
        // Each vertex is in a separate row
        s += "\n";
    }
    return s;
}
Copy the code

Such a simple graph structure, we have achieved

6. Demonstrate

Based on the above code we will demonstrate the operation

const graph = new Graph()
graph.addVertex(2)
graph.addVertex(1)
graph.addVertex(3)
graph.addVertex(0)
graph.addEdge(0.1)
graph.addEdge(0.2)
graph.addEdge(1.2)
graph.addEdge(2.3)
console.log(graph.toString());
Copy the code

Output tactics

Meet our expectations, complete the package

LeetCode actual combat

Recommend a few LeetCode topics on graph structure

65. Significant figures

417. Pacific Atlantic current problems

133. Cloning figure

207. The curriculum

Find the town judge

📖 summary

In this article we explain in detail the structure of figure, how to represent a graph structure, how to write a graph structure, bloggers in his blog, also can learn many things, from the understanding to the implementation, all need to stand in another Angle to think, how can you clear the contents of the output, also hope that readers can from this series of articles learn something true ~

That’s the end of this article, and I’m sure you’ll learn a lot from it. Next, we will start the algorithm. We may not update this part of the content for a while. Please wait patiently

You are welcome to follow this column and stay tuned for the latest articles

The rest of this column

Start here 👉 [Dissolving data Structures] Start here with data structures and algorithms

Stack 👉 what is a stack? Handwriting a stack structure!

Queue 👉 explain queue, priority queue, circular queue, and implement a queue

Linked list 👉 [dissolve data structure] explain linked list structure in detail, and implement a linked list

Set 👉 [dissolve data structure] detail set structure, and realize a set

Dictionary 👉 [resolve data structure] detail dictionary structure, and implement a dictionary

Tree 👉 [resolve data structure] detail tree structure, and achieve binary search tree

Heap 👉 [dissolve data structure] detail heap structure, and realize the minimum heap structure

🐣 eggs

The road of data structure and algorithm is not over yet, the end of this article, but also the end of the basic data structure, in the data structure, there are relatively many advanced content is not involved, such as the implementation of hash table, monotone stack, red black tree, AVL tree and so on… These contents need us to continue to learn in the future, continue to accumulate, in order to have more harvest, in the future, I hope to learn with you, exchange, common progress ~

Thank you very much for your reading and communication in recent days

At the same time, I am very grateful for my sister’s help and encouragement on Monday. I am very glad to meet 🌹 on the front-end road

Finally, I may not be clear enough in many places, please forgive me

💌 if the article has any mistakes, or have any questions, welcome to leave a message, also welcome private letter exchange