No.5: 广度优先算法与深度优先算法

场景

• 深拷贝
• 数组扁平化
• 树节点过滤
  ```javascript function Graph() { this.nodes = []; this.edges = new Map(); }

Graph.prototype.setNode = function (node) { this.nodes.push(node); this.edges.set(node, []); }

Graph.prototype.setEdge = function (from, to) { this.edges.get(from).push(to); this.edges.get(to).push(from); }

Graph.prototype.show = function () { this.nodes.map(item => { console.log(item, ‘->’, Array.from(this.edges.get(item)).join(‘,’)) })

}

// 深度优先算法 Graph.prototype.dfs = function (key) { let marked = {}; const visit = node => { console.log(node); marked[node] = true; let neighbours = Array.from(this.edges.get(node)); neighbours.forEach(neighbour => { if (!marked[neighbour]) { visit(neighbour); } }) }

this.nodes.forEach(node => {
    if (!marked[node]) {
        visit(node);
    }
})

}

// 广度优先算法 Graph.prototype.bfs = function (key) { let marked = {};

const visit = node => {
    let neighbours = this.edges.get(node);
    neighbours.forEach(neighbour => {
        if (!marked[neighbour]) {
            console.log(neighbour);
            marked[neighbour] = true;
        }
    })
}
this.nodes.forEach(node => {
    if (!marked[node]) {
        console.log(node);
        marked[node] = true;
        visit(node);
    }
})

}

let g = new Graph(); g.setNode(‘1’); g.setNode(‘2’); g.setNode(‘3’); g.setNode(‘4’); g.setNode(‘5’); g.show() g.setEdge(‘1’, ‘2’); g.setEdge(‘1’, ‘3’); g.setEdge(‘2’, ‘4’); g.setEdge(‘3’, ‘5’); g.show()

console.log(-------------------------------------------dfs-------------------)

g.dfs(); console.log(-------------------------------------------bfs-------------------)

g.bfs();

```