preface
We have an undirected tree, which describes the hierarchical relationships between countries, provinces, cities, and districts, and we want to find a node in the graph, which level is it in the graph, what do you do?
This article will explain breadth-first search in detail in graphic form and implement it in JavaScript to complete the problems described above. Interested developers are welcome to read this article.
concept
Breadth-first search is an algorithm that searches a graph.
Suppose we start at a node (the starting point) without knowing the overall structure of the graph, and our goal is to start at the starting point and follow the edges until we reach the specified vertex (the end point). In this process, each vertex is reached, it will determine whether it is the end. Breadth-first searches start first at the vertex near the starting point.
This article covers graphs and queues, and for developers who are not familiar with this, I have two other articles to read: Graphs & Stacks and Queues
The illustration example
As shown in the figure, A is the starting point and G is the ending point. We’re starting at A, and we don’t know where G is.
- Set the three vertices B, C and D that can be known from A as the alternate vertices for the next step
- Select one vertex from the alternate vertices. The vertex that is first called a candidate is preferred. If there are multiple vertices called a candidate, you can choose one of them at will.
- Here B, C, and D are all candidates, so we randomly choose the leftmost vertex B.
- Move the starting point to vertex B, turn B red, and turn the already searched vertices orange.
- Let E and F, two vertices that can be directly accessed from B, be alternate vertices
- So the earliest candidates are C and D, and we pick C on the left.
- Move the vertex to C
- Set H, the vertex that can be reached directly from C, as the alternate vertex
- Repeat until the end point is reached or all vertices are traversed.
- At this point, our vertex reaches E, and its search order from A to E is:
A -> B
A -> C
A -> D
B -> E
Copy the code
- I’ve done the search from A to I, and now the vertex is at J
- When terminal G is reached, the search ends
# From vertex A to endpoint G, search in the following order
A -> B
A -> C
A -> D
B -> E
B -> F
C -> H
D -> I
D -> J
E -> K
F
H -> G
Copy the code
❝
Breadth-first search is characterized by extensive search from the beginning to the near and far. Therefore, the closer the target vertex is to the starting point, the faster the search ends.
❞
Implement breadth-first search with JS
As illustrated in the illustrated example, breadth-first search starts with a vertex, searches its children extensively, puts the children into the candidate vertices, determines whether the current vertex is the end point, and if it is not, extracts the data in the candidate vertices in order to perform the above operations until the end point is found.
When we operate candidate nodes, we remove candidate nodes sequentially, in accordance with the data structure: “Queue characteristics” (fifo)
Therefore, we need to implement a queue to store candidate nodes
- Implement a queue for storing candidate nodes
/ * *
* Implement a base queue
* @constructor
* /
const Queue = function () {
// Initialize the queue with an array
let items = [];
// Insert elements into the queue
this.enqueue = function (elem) {
items.push(elem);
}
// Remove the element from the header
this.dequeue = function () {
return items.shift();
}
// View the header element
this.front = function () {
return items[0];
}
// Check whether the queue is empty
this.isEmpty = function () {
return items.length ===0;
}
// Check the queue length
this.size = function () {
return items.length;
}
// View the elements in the queue
this.print = function () {
return items.toString();
}
}
Copy the code- Declare a function with parameters: tree to find, node to find
- Instantiate a queue, declare the vertex to target node depth variable and initialize to 0
- Enqueue the tree
- The queue is traversed until it is empty or the destination node is found
- The depth from the vertex to the destination node is +1 each time
- Iterate over the elements in the queue
- Returns the current depth if the element in the current queue is equal to the target element
- If not, it checks whether there is a next layer and adds the pre-selected node of the next layer to the queue
- Delete the traversed node
❝
Let’s translate this idea into code
❞
/ * *
* Breadth first search
* @param tree Specifies the tree to find
* @param target Specifies the node to look for
Returns {number} returns the depth of the target node in the tree
* /
const breadthFirstSearch = function (tree,target) {
// instantiate a queue
let queue = new Queue();
// The depth of the root node to the target node
let step = 0;
/ / team
queue.enqueue(tree);
// Traverse the queue until it is empty or the destination node is found
while(! queue.isEmpty()){
step += 1;
let len = queue.size();
for (let i = 0; i < len; i++){
// Get the first element
let teamLeader = queue.front();
// Return the current depth if it is the target element
if(target === teamLeader.value) return step;
// If not, add the next node to the queue
if(teamLeader.children && teamLeader.children.length){
teamLeader.children.map(item= >{
queue.enqueue(item);
});
}
// Delete the traversed node
queue.dequeue();
}
}
}
Copy the code❝
Next, let’s use an example to test our breadth-first search function
❞
As shown in the figure below, it is an undirected map that describes the corresponding relations among countries, provinces, cities and districts. Our question is: Which floor is Tianhe District located in from the map?
- To prepare data
// We use JSON to describe the above undirected graph
const dataTree = {
name:"Country".
value:"China".
children: [
{
name:"Province".
value:"Guangdong".
children: [
{
name:"City".
value:"Guangzhou".
children: [
{
name:"Administrative district".
value:"Tianhe District".
},
/// the other parts are omitted ////
]
},
{
name:"City".
value: "Shenzhen".
children: [
{
name:"Administrative district".
value: "Futian District"
},
/// the other parts are omitted ////
]
}
]
},
{
name:"Province".
value:"Shaanxi".
children: [
{
name:"City".
value: "Xi 'an".
children: [
/// the other parts are omitted ////
]
},
{
name:"City".
value: "Practical".
children: [
/// the other parts are omitted ////
]
}
]
}
]
}
Copy the code- Test the breadth-first search function
let step = breadthFirstSearch(dataTree,"Tianhe District");
console.log(The target node is the first node in the graph${step}Layer `);
Copy the code
Write in the last
- The pictures used in this article are from “my first algorithm book”, if infringement, please leave a message in the comment section, the author immediately delete the relevant pictures.
- If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
- This article was first published in nuggets. Reprint is prohibited without permission 💌