数据结构-图-bfs

图的宽度优先遍历

图的宽度优先遍历类似于树的宽度优先遍历，都是先遍历根，然后找到这个节点的邻近节点，通过一个 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;

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG

图的宽度优先遍历

CATALOG

FEATURED TAGS

FRIENDS