图的宽度优先遍历
图的宽度优先遍历类似于树的宽度优先遍历，都是先遍历根，然后找到这个节点的邻近节点，通过一个 queue 来保存这些节点，通过遍历这个 queue，重复以上过程，则可以实现
代码实现
class BFCComponent {
constructor(g, s) {
this.g = g;
this.s = s;
this.visited = new Array(g.V()).fill(false);
this.from = new Array(g.V()).fill(-1);
this.org = new Array(g.V()).fill(-1);
this.bfs();
}
bfs() {
const queue = [this.s];
this.visited[this.s] = true;
this.org[this.s] = 0;
while (queue.length) {
const top = queue.shift();
for (const i of this.g.adj(top)) {
if (!this.visited[i]) {
queue.push(i);
this.visited[i] = true;
this.from[i] = top;
this.org[i] += 1;
}
}
}
}
hasPath(w) {
if (!(v >= 0 && v < this.g.V())) {
throw new Error('Out of boundary!');
}
return this.visited[w];
}
showPath(w) {
const stack = [];
let p = w;
while (p !== -1) {
stack.push(p);
p = this.from[p];
}
const queue = [];
while (stack.length) {
queue.push(stack.pop());
}
console.log('path: ', queue.join(' -> '));
}
length(v) {
if (!(v >= 0 && v < this.g.V())) {
throw new Error('Out of boundary!');
}
return this.ord[v];
}
}
module.exports = BFCComponent;