节点js中的图形数据结构 [英] graph data structure in node js

问题描述

更新1：

我在 https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9 ，但我正在错误 TypeError：无法读取未定义的属性 left 。你能告诉我如何解决它吗？

I found an example of BFS here https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9, but I am getting an error TypeError: Cannot read property 'left' of undefined. can you tell me how to fix it

function roadsAndLibraries(n, c_lib, c_road, cities) {
    console.log("roadsAndLibraries n--->", n);
    console.log("roadsAndLibraries c_lib--->", c_lib);
    console.log("roadsAndLibraries c_road--->", c_road);
    console.log("roadsAndLibraries cities--->", cities);
    var m = new Map();
    m.set('a', 2);
    m.set('b', 3);
    m.set('b', 3);
    m.set('b', 2);
    m.set('b', 1);

    console.log("map value--->", m);
        // Check that a root node exists.

    // if (rootNode === null) {
    //     return;
    // }

    // Check that a root node exists.
    if (n === null) {
        console.log("n root node--->", n);
        return;
    }

    // Create our queue and push our root node into it.
    // var queue = [];
    // queue.push(rootNode);

    // Create our queue and push our root node into it.
    var queue = [];
    queue.push(n);

    console.log(" queue.push--->", queue);


    while (queue.length > 0) {
        // Create a reference to currentNode, at the top of the queue.
        var currentNode = queue[0];

        // If currentNode has a left child node, add it to the queue.
        if (currentNode.left !== null) {
            queue.push(currentNode.left)
        }
        // If currentNode has a right child node, add it to the queue.
        if (currentNode.right !== null) {
            queue.push(currentNode.right)
        }
        // Remove the currentNode from the queue.
        queue.shift()
    }




}

• 我正在尝试解决黑客排名的图数据结构问题。


• 我的方法应返回



• 在此处提供我的黑客排名问题
  https://www.hackerrank.com/challenges/torque-and-development/problem?h_l=interview&playlist_slugs%5B%5D%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D%5B%5D= graphs& isFullScreen = true

  我调试已经存在的代码，并从示例输入中发现以下值正在打印
  2
  3 3 2 1

  I debugged already exisitng code and found from sample input following values are printing 2 3 3 2 1

  我看了本教程并理解了这些概念，但仍无法继续
  https://medium.com/@ziyoshams/graphs-in-javascript-cc0ed170b156

  I looked at this tutorial and understood the concepts but still not able to proceed further https://medium.com/@ziyoshams/graphs-in-javascript-cc0ed170b156

  在下面提供我的调试代码和调试输出

  Provding my debugged code and debugged output below

  图形代码

  'use strict';
  
  const fs = require('fs');
  
  process.stdin.resume();
  process.stdin.setEncoding('utf-8');
  
  let inputString = '';
  let currentLine = 0;
  
  process.stdin.on('data', inputStdin => {
      inputString += inputStdin;
  });
  
  process.stdin.on('end', function() {
      inputString = inputString.replace(/\s*$/, '')
          .split('\n')
          .map(str => str.replace(/\s*$/, ''));
  
      main();
  });
  
  function readLine() {
      return inputString[currentLine++];
  }
  
  // Complete the roadsAndLibraries function below.
  function roadsAndLibraries(n, c_lib, c_road, cities) {
      console.log("roadsAndLibraries n--->", n);
      console.log("roadsAndLibraries c_lib--->", c_lib);
      console.log("roadsAndLibraries c_road--->", c_road);
      console.log("roadsAndLibraries cities--->", cities);
  
  var m = new Map();
      m.set('a', 2);
      m.set('b', 3);
      m.set('b', 3);
      m.set('b', 2);
      m.set('b', 1);
  
      console.log("map value--->", m);
  
  
  
  
  
  }
  
  function main() {
      const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
      console.log("ws--->", ws);
  
  
      const q = parseInt(readLine(), 10);
      console.log("q--->", q);
  
      for (let qItr = 0; qItr < q; qItr++) {
          const nmC_libC_road = readLine().split(' ');
          console.log("nmC_libC_road--->", nmC_libC_road);
  
          const n = parseInt(nmC_libC_road[0], 10);
          console.log("n--->", n);
  
  
          const m = parseInt(nmC_libC_road[1], 10);
          console.log("m--->", m);
  
          const c_lib = parseInt(nmC_libC_road[2], 10);
          console.log("c_lib--->", c_lib);
  
          const c_road = parseInt(nmC_libC_road[3], 10);
          console.log("c_road--->", c_road);
  
          let cities = Array(m);
          console.log("cities--->", cities);
  
          for (let i = 0; i < m; i++) {
              cities[i] = readLine().split(' ').map(citiesTemp => parseInt(citiesTemp, 10));
          }
  
          const result = roadsAndLibraries(n, c_lib, c_road, cities);
          console.log("result--->", result);
  
          ws.write(result + '\n');
      }
  
      ws.end();
  }
  

  样本输出

  ws---> WriteStream {
    _writableState:
     WritableState {
       objectMode: false,
       highWaterMark: 16384,
       finalCalled: false,
       needDrain: false,
       ending: false,
       ended: false,
       finished: false,
       destroyed: false,
       decodeStrings: true,
       defaultEncoding: 'utf8',
       length: 0,
       writing: false,
       corked: 0,
       sync: true,
       bufferProcessing: false,
       onwrite: [Function: bound onwrite],
       writecb: null,
       writelen: 0,
       bufferedRequest: null,
       lastBufferedRequest: null,
       pendingcb: 0,
       prefinished: false,
       errorEmitted: false,
       emitClose: false,
       bufferedRequestCount: 0,
       corkedRequestsFree:
        { next: null,
          entry: null,
          finish: [Function: bound onCorkedFinish] } },
    writable: true,
    _events: [Object: null prototype] {},
    _eventsCount: 0,
    _maxListeners: undefined,
    path:
     '/tmp/submission/20190610/18/32/hackerrank-e7eb8e7be2993c28875aad2bbb8d6292/0.userout',
    fd: null,
    flags: 'w',
    mode: 438,
    start: undefined,
    autoClose: true,
    pos: undefined,
    bytesWritten: 0,
    closed: false }
  q---> 2
  nmC_libC_road---> [ '3', '3', '2', '1' ]
  n---> 3
  m---> 3
  c_lib---> 2
  c_road---> 1
  cities---> [ <3 empty items> ]
  roadsAndLibraries n---> 3
  roadsAndLibraries c_lib---> 2
  roadsAndLibraries c_road---> 1
  roadsAndLibraries cities---> [ [ 1, 2 ], [ 3, 1 ], [ 2, 3 ] ]
  result---> undefined
  nmC_libC_road---> [ '6', '6', '2', '5' ]
  n---> 6
  m---> 6
  c_lib---> 2
  c_road---> 5
  cities---> [ <6 empty items> ]
  roadsAndLibraries n---> 6
  roadsAndLibraries c_lib---> 2
  roadsAndLibraries c_road---> 5
  roadsAndLibraries cities---> [ [ 1, 3 ], [ 3, 4 ], [ 2, 4 ], [ 1, 2 ], [ 2, 3 ], [ 5, 6 ] ]
  result---> undefined
  

  
  

  推荐答案

  在我看来，您好像遇到了麻烦了解问题所在。我将尝试对其进行总结，并指出一些您需要考虑的事项。

  It seems to me as though you are having trouble understanding what the problem is about. I will try to summarize it and point out a few things you need to consider.

  城市图

  您会得到一个其中每个节点都是城市的图一条边缘是两个城市之间的双向道路。这意味着您正在处理一个无向图，这意味着如果城市A和B之间有一条边（=道路），则可以从A到B以及从B到A行驶。当然，您可以通过为每条道路创建两条边来用有向图表示这一点：一条从A到B，一条从B到A。但是我认为这不是必需的。

  You are given a graph where each node is a city and an edge is a bidirectional road between two cities. This means you are dealing with an undirected graph, meaning if there is an edge(=road) between cities A and B, you can travel from A to B and from B to A. Of course you can represent this in terms of directed graph by creating two edges for each road: one from A to B and one from B to A. But I don't think this is necessary.

  现在，您希望每个城市都拥有一个图书馆或通往拥有图书馆的城市的道路。您意识到，如果有两套未通过任何道路连接的城市，那么每套城市都将至少需要一个图书馆。这样的城市集称为连接图的组件。您将需要识别这些组件。它们将成为必须独立解决的问题的一部分。

  Now, you want every city to either have a library or have a path to a city with a library. You realize that if you have two sets of cities that are not linked by any road, you will need at least one library for each of these sets. Such sets of cities are called connected components of a graph. You will need to identify these components. They will be parts of the problem that have to be solved independently.

  访问图书馆的费用

  第二个信息是在城市中重建图书馆的成本以及修路的价格。当您试图最小化总成本时，这意味着您正在尝试重建尽可能少的道路和尽可能少的库。

  The second information you are given is the cost of rebuilding a library in a city and the price of repairing a road. As you are trying to minimize the total cost, this means that you are trying to rebuild as few roads a possible and as few libraries as possible.

  您意识到如果重建图书馆的费用小于或等于修路的费用，则更便宜的选择是在每个城市建立图书馆。

  You realize that if the cost of rebuilding a library is less than or equal to the cost of building a road, the cheaper option is to build a library at every city.

  在其他情况下，解决方案相当简单，但不那么容易看到。让我们考虑一个连接的组件。对于商品，假设城市A，B，C和D是此关联组件的节点。

  In other cases, the solution is fairly simple but not as easy to see. Let's consider a single connected component. For commodity, let's assume that cities A, B, C and D are the nodes of this connected component.

  A----B
  |    |
  C----D
  

  您已经知道需要放置至少一个在其中一个城市的图书馆。让我们在城市A上放置一个图书馆。然后，由于我们处于连接的组成部分中，所以A有一些通往其他城市的道路（最少一条，最多3条）。对于具有将其连接到城市A的道路的城市，重建道路比建立新图书馆要便宜。因此，我们选择重建道路。现在，城市A和城市A的邻居（城市B和D）可以访问图书馆。然后，在A的邻居（城市B和C）中，将有通往尚未使用图书馆的城市的道路。在这种情况下，C和B都有通往D的道路。我们只需要一条道路就可以将D连接到A的图书馆。同样，修建一条通往可以访问图书馆的城市的道路要比修建道路便宜一个新的图书馆。

  You already know you will need to place at least one library on one of the cities. Let's place a library on city A. Then, as we are in a connected component, A has some roads (minimum one, maximum 3) that go to other cities. For the cities that have a road that connects them to city A, it is cheaper to rebuild the road than to build a new library. So we choose to rebuild the road. Now city A and the neighbors of A (cities B and D) can access a library. Then, among the neighbors of A (cities B and C), there will be roads to cities that do not yet have access to a library. In this case, both C and B have a road to D. We will only need one road to connect D to the library in A. Again, it is cheaper to build a road to a city that can access to a library than to build a new library.

  算法

  以前通过扩散到所有邻居逐渐连接城市的方法第一节点的邻居，则第一节点的邻居的邻居（递归）是BFS。另外，BFS算法适用于查找图的连接部分。

  The previous method of gradually connecting cities by spreading to all neighbors of the first node, then the neighbors of the neighbors of the first nodes (recursively) is a BFS. As a bonus, the BFS algorithm is suitable for finding connected components of a graph.

  如果您理解前面的解释，我认为您能够解决问题。您可以在图形上运行BFS算法。启动算法时，先计算1个图书馆，然后在每次连接到新城市时计算1条道路。当您完成BFS算法后，图中仍然有您尚未访问的城市时，请计算一个额外的图书馆，然后从尚未浏览的城市开始再次使用BFS。

  If you understood the previous explanations, I think you are able to solve the problem. You can run a BFS algorithm on the graph. When you start the algorithm, count 1 library, and then 1 road each time you connect to a new city. When you finish your BFS algorithm but there are still cities in the graph that you have not visited, count an additional library and use BFS again starting from a city that you haven't explored yet.

  这篇关于节点js中的图形数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！