数据结构图有那些应用场景呢?

张仪ranck
  • 353

数据结构图有那些应用场景呢?
不限于前端,后端,数据库,任何场景,请尽可能告诉我最真实的使用场景;
我正在学习这个知识点,我需要更多的场景练习加深记忆灵活掌握,也希望可以给浏览者提供思路,而不只是死记硬背住概念;
另外,breadthFirstSearch 方法,写在Graph内部比较合适,还是如下写在外部比较合适呢
再次感谢


class Graph {
  constructor() {
    this.isDirected = false;
    this.vertices = []; // 顶点
    this.adjList = new Dictionary(); // 邻边
  }

  addVertex(v) {
    if (!this.vertices.includes(v)) {
      this.vertices.push(v);
      this.adjList.set(v, []);
    }
  }

  addEdge(v, w) {
    if (!this.vertices.includes(v)) {
      this.vertices.push(v);
    }
    if (!this.vertices.includes(w)) {
      this.vertices.push(w);
    }
    this.adjList.get(v).push(w);
    if (!this.isDirected) {
      this.adjList.get(w).push(v);
    }
  }

  getVertices() {
    return this.vertices;
  }
  getAdjList() {
    return this.adjList;
  }

  // breadthFirstSearch(first) {}

  toString() {
    let result = "";

    for (let i = 0; i < this.vertices.length; i++) {
      const vertex = this.vertices[i];
      const adjList = this.adjList.get(vertex);
      result += `${vertex} => ${adjList} \n`;
    }
    return result;
  }
}

function initMark(vertices) {
  const map = {};
  for (let i = 0; i < vertices.length; i++) {
    map[vertices[i]] = false;
  }
  return map;
}

function breadthFirstSearch(graph, startVertex, callback) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();

  const eachMap = initMark(vertices);
  const queue = new Queue();
  queue.enqueue(startVertex);

  while (!queue.isEmpty()) {
    const u = queue.dequeue();
    const neighbors = adjList.get(u);
    eachMap[u] = true;
    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i];
      if (!eachMap[neighbor]) {
        eachMap[neighbor] = true;
        queue.enqueue(neighbor);
      }
    }
    if (typeof callback === "function") {
      callback(u);
    }
  }
}
回复
阅读 269
1 个回答

挺多的吧,地图导航,JavaScript GC标记回收,字节自研的图数据库,不都是图的应用嘛

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏