一次代码重构 JavaScript 图连通性判定

简介

说重构其实就是整理了代码，第一次自己手写写的很丑，然后看了书上写的，虽然和书上的思路不同但是整理后几乎一样漂亮

效果

整体代码如下

class Node {

  AdjNodes = new Set()

  id = ""

  constructor(id) { this.id = id }

  connect(node) {

    this.AdjNodes.add(node)

    node.AdjNodes.add(this)

  }

}

class RandomGraph {

  nodes = new Set()

  constructor(size) {

    for (let i = 0; i < size; i++) {

      this.nodes.add(new Node(i))

    }

    const threshold = 1 / size

    for (const x of this.nodes)

      for (const y of this.nodes)

        if (Math.random() < 1 / size)

          x.connect(y)

  }

  print() {

    for (const i of this.nodes) {

      let ids = [...i.AdjNodes]

        .map(x => x.id)

        .join(',')

      console.log(`${i.id}:${ids}`)

    }

  }

  ifConnected() {

    const visit = new Map()

    function* recur(node) {

      if (visit.has(node)) return

      yield node

      for (const x of node.AdjNodes) {

        yield* recur(x)

      }

    }

    let v = this.nodes[Symbol.iterator]().next().value

    for (const i of recur(v))

      visit.set(i)

    return visit.size === this.nodes.size

  }

}

let g = new RandomGraph(6)

g.print()

console.log(`g.ifConnected:${g.ifConnected()}`);

修改之前的代码：

ifConnected() {

  for (const [v,_] of this.nodes.entries()) {

    let visit = new WeakMap()

    function* recur(node) {

      if (visit.has(node)) return

      yield (()=>{

        visit.set(node)

        return node

      })();

      for(const [x] of node.AdjNodes.entries()) {

        yield* recur(x)

      }

    }

    const a = new Set()

    for (const i of recur(v)) {

      console.log(i)

      a.add(i)

    }

    console.log(`node:${v.id} minG.size:${a.size}`)

    if (a.size === this.nodes.size) return true

    return false

  }

}

巴特西

一次代码重构 JavaScript 图连通性判定

简介

效果

整体代码如下

修改之前的代码：

最新文章

热门文章