数据结构-图-dfs

图的深度优先遍历

图的 dfs 跟树的 dfs 类似，都是从一个顶点一直遍历到不可遍历为止，通过 dfs 可以求出图的联通分量，每个顶点的联通分量

代码实现

class DFSComponent {
  constructor(g) {
    this.g = g;
    this.visited = new Array(g.V()).fill(false);
    this.id = new Array(g.V()).fill(-1);
    this.ccount = 0;

    for (let i = 0; i < g.V(); i++) {
      if (!this.visited[i]) {
        this.dfs(i);
        this.ccount++;
      }
    }
  }

  dfs(v) {
    this.visited[v] = true;
    this.id[v] = this.ccount;
    for (const i of this.g.adj(v)) {
      if (!this.visited[i]) {
        this.dfs(i);
      }
    }
  }

  count() {
    return this.ccount;
  }

  isConnected(v, w) {
    if (!(v >= 0 && v < this.g.V())) {
      throw new Error('Out of boundary!');
    }
    if (!(w >= 0 && w < this.g.V())) {
      throw new Error('Out of boundary!');
    }
    return this.id[v] === this.id[w];
  }
}

module.exports = DFSComponent;

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