• Graph Data Structure Implementation in JavaScript
• Before Semicolon
• The Nuggets translation Project
• Permanent link to this article: github.com/xitu/gold-m…
• Translator: CarlosChenN
• Proofread by: Z Hoarfroster

JavaScript implements graph data structures

Graph data structures help us create a lot of powerful things, and the likelihood that you can use them to implement non-linear data structures is high. It is often used for multiple complex connections between many data nodes, which makes it particularly suitable for showing maps, networks, and navigation systems.

The video explanation of this article

This article is a detailed and improved version of Youtube’s data structure series above, if you like the video, you can click on the URL above to watch the original video.

Watch the video

What is a graph?

A graph is a nonlinear abstract data structure, meaning that it is defined by behavior, not by an emphatic data model.

It consists of a set of nodes — also known as vertices connected by edges (lines). If the vertices are oriented, the graph is called a directed graph. Two nodes are said to be strongly connected if their edges point to each other.

Edges can also have weights, which means edges also have values, which is very useful information when you’re representing a map. For example, if we think of edges as roads and positions as nodes, we can give the distance values of these edges, and we can know how far one node is from the other by adding the values of the edges between the nodes.

When to use graph data structures?

In a list data structure, you have an ordered collection of elements that you need to traverse one by one until you find the one you want. In a hierarchical data structure like a tree, you have parent-child relationships that allow you to decide which subtrees to navigate to. In a graph data structure, you have adjacent points.

In a diagram, an element (or node) only knows the nodes to which it connects, which connect more nodes, and so on. This type of complex relationship is the main characteristic of data that needs to be graphically represented.

GPS systems and maps, for example, can be represented by graphs, which connect many nodes together so that they can help determine how to get from one point to another, and how far or how far apart they are.

Social networks take people as nodes and can be graphed, for example, to help figure out how many friends or interests two people have in common by checking who they are connected to

The Internet is a big picture, and search engines use graphs to determine the connections between websites.

A graph is needed when there are complex relationships between nonlinearities or layers. To be clear, a linear data structure has a start node and an end node, and a hierarchical structure has a start node and many end nodes, depending on which path you follow. Diagrams have multiple start nodes and end nodes. If your data follows this pattern, you may need diagrams.

Simple implementation diagram

Diagrams are used to represent complex data relationships, but the implementation of the diagram itself is very simple.

One thing you might need to understand is the concept of matrices and adjacency lists. For example, the simple graph below can be represented as an adjacency matrix or an adjacency list, or even an association matrix, depending on what type you want to represent and what you want to do with it.

• An adjacency matrix is like a table with a 1 for nodes connected and a 0 for nodes not connected. This approach is well suited to representing finite graphs.
• An adjacency list is similar to a dictionary where each node value is a list of all nodes to which it is connected. This is another way of representing finite graphs that is faster and easier to process.
• An association matrix is also like a table, except that it tracks whether two nodes are connected or not. It tracks the direction of edges. 1 means it uses edges to connect other nodes, -1 means other nodes use edges to connect it, and 0 means edges that are not connected to this node. This is great for maps and navigation systems when you have edges with directions and values (weights).

For the implementation of this graph, WHICH I’m going to simplify with an adjacency list, the graph I’m going to show you is generic, unweighted.

We’ll start by declaring a graph class with a private list of vertices that uses the set data structure to ensure that it does not contain duplicate edges, and a private adjacency list that uses the Map data structure to track node connections.

class Graph {
  #vertices = new Set();
  #adjacentList = new Map();
  
  get vertices() {
    return Array.from(this.#vertices)
  }
  
  get adjacentList() {
    const list = {};
    
    this.#adjacentList.forEach((val, key) => {
      list[key] = Array.from(val)
    })
    
    return list
  }
}
Copy the code

Since they are private, I use getters to return them, and I first convert them to arrays and JavaScript objects because they are easier and more commonly used, and it also prevents changing those private values externally.

Next, we need a way to add vertices.

class Graph { ... addVertex(vertex = null) { if( ! this.#vertices.has(vertex) && vertex ! == null && vertex ! == undefined ) { this.#vertices.add(vertex); this.#adjacentList.set(vertex, new Set()); }}}Copy the code

All these methods do is make sure that each vertex is not empty and has not been added before. It is then added to the list of vertices and mapped with an empty Set as the value.

Now we need a way to add edges.

class Graph { ... addEdge(vertex1 = null, vertex2 = null, directed = true) { if( vertex1 ! == null && vertex1 ! == undefined && vertex2 ! == null && vertex2 ! == undefined && vertex1 ! = vertex2 ) { this.addVertex(vertex1); this.addVertex(vertex2); this.#adjacentList.get(vertex1).add(vertex2); if(directed) { this.#adjacentList.get(vertex2).add(vertex1); }}}}Copy the code

The first thing to do is make sure that the vertices are different from each other and not empty. After that, we add them to the list of vertices, which checks to see if the vertices are in the list before adding them. It does this by adding Vertex2 to the vertex1 adjacency list, which means that Vertex1 connects to Vertex2, and if it is directional, it also makes vertex2 connect to vertex1 in both directions.

With it, the graph has everything we want and need.

Width first traversal

When you have any kind of data structure, there is a need to search for these items (nodes in this case), and one way to search for nodes in a graph is to use a width-first search.

This type of search or traversal is known in the field of tree data structures, and tree traversal is a graph traversal.

For this graph, we will use the concept of color to keep track of whether we have finished checking the adjacency list of nodes and to avoid visiting a node multiple times for efficiency.

The concept is simple, all nodes are green by default, one node turns yellow when you check it, and red when you visit all of its neighbors.

const COLORS = Object.freeze({
  GREEN: 'green',
  YELLOW: 'yellow',
  RED: 'red'
});
Copy the code

When you do a width-first traversal, you check all the adjacent nodes, and when you check, you create a queue that has the next node to check.

Note: Whenever a check is mentioned, it simply means that a node value is being read. When we say access, it means we are checking its list of adjacent nodes.

The following function takes a graph we just implemented and the vertices to start looking for, and a callback function that will be called when we examine the nodes.

function breathFirstSearch(graph, fromVertex, callback) { const {vertices, adjacentList} = graph; if(vertices.length === 0) return; const color = vertices .reduce((c, v) => ({... c, [v]: COLORS.GREEN}), {}); const queue = []; queue.push(fromVertex); while(queue.length) { const v = queue.shift(); const nearVertex = adjacentList[v]; color[v] = COLORS.YELLOW; nearVertex.forEach(w => { if(color[w] === COLORS.GREEN) { color[v] = COLORS.YELLOW; queue.push(w); }}); color[v] = COLORS.RED; callback && callback(v); }}Copy the code

It starts by deconstructing the vertices and the adjacent list, which is going to be an array and an object, because that’s what we defined in the getter. If there are no vertices, it does nothing and returns. Then, we color all the nodes green, which is basically a vertex-to-color mapping, so we can easily query the color of the nodes

Queues are used to keep track of the next vertex to be accessed, and from the beginning, the vertex provided is the first vertex to be accessed. Review the queue data structure article to see how it works.

When there is something in the queue, we move the queue to get the preceding vertex, get the list of nodes adjacent to it, and color it yellow because we have checked its value. The vertices of each loop are queued up for the next visit, and as long as they are green, we color them yellow.

Since we check all of the list of adjacent vertices, we can color it red because it is already fully accessed and call the callback function with its value. At this point, there should be something in the queue, and if there is, the process will continue.

Depth-first traversal

Depth-first traversal works a little differently. Instead of checking all adjacent list nodes before accessing the next node in the queue, it accesses the node immediately when it is checked using the stack data structure to track which node to check next.

The same color concept is used here, and his implementation is based on recursive functions rather than the while loop used in the width-first search algorithm. It looks something like this:

function depthFirstSearch(graph, fromVertex, callback) { const {vertices, adjacentList} = graph; if(vertices.length === 0) return; const color = vertices .reduce((c, v) => ({... c, [v]: COLORS.GREEN}), {}); callback && callback(fromVertex); color[fromVertex] = COLORS.YELLOW; function visit(v) { if(color[v] === COLORS.GREEN) { callback && callback(v); color[v] = COLORS.YELLOW; adjacentList[v].forEach(visit); } color[v] = COLORS.RED; } adjacentList[fromVertex].forEach(visit); }Copy the code

This function takes the same parameters as the width-first search function and performs the same checks and color Settings. After coloring all nodes green, it calls the callback function for the first vertex and then colors it yellow because it is being checked.

It declares an access recursive function that calls the adjacent nodes of each current vertex. This accessor checks to see if the node is green, unchecked or not accessed, calls the callback function, colors it yellow, and then grabs the adjacent lists, calling itself again one by one.

It can color the nodes red only after it has checked all the neighboring list nodes and their neighbors, and so on. It searches in depth before dealing with nodes, which is why it is called a depth-first search algorithm.

See all the code for this article

conclusion

As a developer, being familiar with all the different data structures and understanding how to work with them is critical to moving into the next phase of your career, but at the same time being able to apply different data structure algorithms requires a different mindset to solve any programming problem.

If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.

---

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.