使用 JavaScript 生成随机树

Question

我正在开展一个项目，以生成随机数据结构来测试 DSA 问题的解决方案。我正在尝试形成一种算法，该算法生成随机树数据结构，该数据结构接受 测试用例数 和 节点数 的输入。由于我无法使用指针和引用，因此我无法在 javaScript.

中弄清楚如何执行此操作

到目前为止，我已经掌握了基础知识，但是，我的代码出现了错误

代码：

const randnumgen = (min, max) => {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min;
};

function randtreegen(nodes) {

  var string = "";

  class Tree {

    constructor(nodes) {
      this.nodes = nodes;
      this.adj = [];
    }
    addEdge(n, w) {
      this.adj[n].push(w);
    }
    removeEdge(n, w) {
      this.adj[n].forEach((elem) => {
        if (elem === w) {
          var index = this.adj[n].indexOf(elem);
          if (index !== -1) this.adj[n].splice(index, 1);
        }
      });
    }
    isCyclicUtil(nodes, visited, recStack) {
      if (visited[nodes] === false) {
        visited[nodes] = true;
        recStack[nodes] = true;

        this.adj[n].forEach((elem) => {
          if (!visited[elem] && this.isCyclicUtil(elem, visited, recStack))
            return true;
          else if (recStack[elem])
            return true;
        });
      }
      recStack[nodes] = false;
      return false;
    }
    isCyclic() {

      visited = new Array();
      recStack = new Array();

      for (var i = 0; i < this.nodes; i++) {
        visited[i] = false;
        recStack[i] = false;
      }

      for (var j = 0; j < this.nodes; i++) {
        if (this.isCyclicUtil(j, visited, recStack))
          return true;
      }

      return false;
    }
  }

  container = new Set();
  let t = new Tree(nodes);
  for (var i = 1; i < nodes - 1; i++) {
    var a = randnumgen(1, nodes);
    var b = randnumgen(1, nodes);
    var p = [a, b];

    t.addEdge(p[0], p[1]);

    while (container.has(`${p[0]},${p[1]}`) || t.isCyclic() === true) {
      t.removeEdge(p[0], p[1]);

      var a = randnumgen(1, nodes);
      var b = randnumgen(1, nodes);
      var p = [a, b];

      t.addEdge(p[0], p[1]);
    }
    container.add(`${p[0]},${p[1]}`);
  }

  container.forEach((elem) => {
    string += elem + '\n'
  });
  return string;
}


function treeGen(test_case, tree_nodes) {
  var result = "";
  while (test_case-- > 0) {
    result += randtreegen(tree_nodes) + '\n';
  }
  return result;
}

const ans = treeGen(1, 5);

document.write(ans);

错误

TypeError: Cannot read property 'push' of undefined at /home/cg/root/7217808/main.js:18
        this.adj[n].push(w);

我的问题是：

逻辑是否正确？
如何解决错误以使其正常工作？

P.S：我参考了 this 关于 GeeksforGeeks 的文章。

Answer 1

主要问题是您没有将 adj 条目创建为空数组。所以改变：

  this.adj = [];

收件人：

  this.adj = Array.from({length: nodes}, () => []); // create that many empty arrays

但还有其他问题：

一些代码段期望节点从 1 开始编号，而其他代码段期望从 0 开始编号。由于数组索引从 0 开始，因此也为节点编号更为自然从 0 开始。
有对未知变量n的引用，应该是nodes。注意：您为该变量选择复数名称很奇怪。
当您 return true 在 forEach 回调中时，您不会 return 来自外部函数，而只能来自 forEach 回调.这不是你想要的。使用 for...of 循环解决此问题。
在 isCyclic 中你在 j 上有一个循环，但是你用 i++ 递增，所以这个循环永远不会结束。做到 j++
循环测试不足以确保你的图是树，因为在有向图中你仍然可以在节点 A 和节点 B 之间有多个路径，没有循环。
创建边的循环需要再迭代一次，所以让它从0开始。

不过，我建议使用一种稍微不同的方法来生成随机树：随机打乱所有节点，并让打乱后的数组中的第一个节点成为树的根。迭代所有其他节点，并让它们成为新边缘的目的地。请注意，在树中没有两条边到达的节点。

然后就可以做循环测试了。然而，我也会做不同的事情：在添加边缘之前执行测试 。您可以获得所选 b 节点的所有后代节点，如果 a 在该集合中，则不应创建边 a,b.

这是您修改后的代码。我删除了不再使用的部分：

function randnumgen (min, max) { min = Math.ceil(min); max = Math.floor(max); return Math.floor(Math.random() * (max - min + 1)) + min; } class Tree { constructor(nodes) { this.nodes = nodes; this.adj = Array.from({length: nodes}, () => []); } addEdge(n, w) { this.adj[n].push(w); } descendants(node) { let visited = new Set([node]); for (let node of visited) { for (let elem of this.adj[node]) { if (!visited.has(elem)) visited.add(elem); } } return visited; } } function shuffle(array) { for (var i = array.length - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var temp = array[i]; array[i] = array[j]; array[j] = temp; } return array; } function randtreegen(nodes) { let t = new Tree(nodes); let [root, ...children] = shuffle([...Array(nodes).keys()]); let edges = []; let a; for (let b of children) { do { a = randnumgen(0, nodes-1); // make zero based } while (t.descendants(b).has(a)); t.addEdge(a, b); edges.push([a, b]); } return edges.join("\n"); } function treeGen(test_case, tree_nodes) { var result = ""; while (test_case-- > 0) { result += randtreegen(tree_nodes) + '\n'; } return result; } const ans = treeGen(1, 5); console.log(ans);

使用 JavaScript 生成随机树

Generate random tree using JavaScript

javascript

algorithm

tree

logic

data-structures

代码：

错误

我的问题是：