数据结构-图-weight sparse graph

有权图-实现稀疏图

有向图的稀疏图实现也跟一般的稀疏图实现类似，主要是把邻接表里面的每个元素换成了 edge

代码实现

const Edge = require("./edge");

class SparseGraph {
  constructor(n, directed) {
    this.n = n;
    this.m = 0;
    this.directed = directed;

    this.g = new Array(n).fill().map(() => new Array());
  }

  V() {
    return this.n;
  }

  E() {
    return this.m;
  }

  hasEdge(v, w) {
    if (!(v >= 0 && v < this.n)) {
      throw new Error('Out of boundary!');
    }
    if (!(w >= 0 && w < this.n)) {
      throw new Error('Out of boundary!');
    }
    for (const item of this.g[v]) {
      if (item.w === w) {
        return true;
      }
    }

    return false;
  }

  addEdge(v, w, weight) {
    const edge = new Edge(v, w, weight);
    this.g[v].push(edge);
    if (v !== w && !this.directed) {
      const edge1 = new Edge(w, v, weight);
      this.g[w].push(edge1);
    }
    this.m++;
  }

  show() {
    for (let i = 0; i < this.n; i++) {
      for (let j = 0; j < this.n; j++) {
        if (this.g[i][j]) {
          console.log('v: ', this.g[i][j].v, 'w: ', this.g[i][j].w, 'weight: ', this.g[i][j].weight);
        }
      }
    }
  }
}

module.exports = SparseGraph;

const sg = new SparseGraph(13, false);
sg.addEdge(0, 1, 1);
sg.addEdge(0, 2, 2);
sg.addEdge(0, 3, 3);
sg.show();

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