JS implements depth-first search and breadth-first search of graphs

This is the 21st day of my participation in Gwen Challenge

We talked about binary tree search, and binary tree search can be extended in many ways, to tree search, graph search, graph search can be extended to crawler logic. Today we take a look at the following search.

Search is divided into two kinds, one is depth first search, one is breadth first search.

Depth-first search follows one edge of a node all the way to black, then returns to the starting node, continues to the next edge, returns if the target node is found, and traverses the entire node if not.

Breadth-first searches go layer by layer. As shown in the figure above, breadth-first search starts from A; if not, search continues from CB of the second layer; if the target node is found, return; if not, all nodes are traversed layer by layer.

Depth-first search is better for exploring the unknown because it goes far first, as far as it can go.

Breadth-first search is better for exploring local areas, for example, if I know there’s something I’m looking for nearby, I’ll look for it layer by layer.

Tree search versus graph search, one of the nice things about trees is that they don’t form loops. The graph will form a circle, so the search of the graph is complicated. If we use the previous method, there may be an infinite loop, so we want to make it search, the searched point no longer find. Let’s use code to implement a depth-first and breadth-first search as shown below.

The code implements the depth-first search of the graph

function Node(value) {
    this.value = value;
    this.neighbor = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");

a.neighbor.push(b);
a.neighbor.push(c);
b.neighbor.push(a);
b.neighbor.push(c);
b.neighbor.push(d);
c.neighbor.push(a);
c.neighbor.push(b);
c.neighbor.push(d);
d.neighbor.push(b);
d.neighbor.push(c);
d.neighbor.push(e);
e.neighbor.push(d);

function deepSearch(node, target, path) {
    if (node == null) return false;
    if (path.indexOf(node) > -1) return false;// Return false if already found
    if (node.value == target) return true;
    path.push(node);
    var result = false;
    for (var i = 0 ; i < node.neighbor.length ; i ++) {
        result |= deepSearch(node.neighbor[i], target, path);
    }
    return result ? true : false;
}

console.log(deepSearch(b, "e"[]));Copy the code

The code implements breadth-first search of the graph

function Node(value) {
    this.value = value;
    this.neighbor = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");

a.neighbor.push(b);
a.neighbor.push(c);
b.neighbor.push(a);
b.neighbor.push(c);
b.neighbor.push(d);
c.neighbor.push(a);
c.neighbor.push(b);
c.neighbor.push(d);
d.neighbor.push(b);
d.neighbor.push(c);
d.neighbor.push(e);
e.neighbor.push(d);

function bfs(nodes, target, path) {
    if (nodes == null || nodes.length == 0) return false;
    var nextNodes = [];
    for (var i = 0 ; i < nodes.length ; i ++) {
        if (path.indexOf(nodes[i]) > -1) continue;// Skip the number if you have already found it
        path.push(nodes[i]);
        if (nodes[i].value == target) return true;
        else nextNodes = nextNodes.concat(nodes[i].neighbor);
    }
    return bfs(nextNodes, target, path);
}

console.log(bfs([c], "b"[]));Copy the code