javascript - 使用 while 循环迭代遍历图

Question

我正在使用 cytoscape.js 创建图表。

我想遍历节点(有方向)，但仅限于那些与包含特定值的边相连的节点。

我是这样用递归完成的

function traverse(node, requiredValue, visitedNodes) {
  // break if we visit a node twice
  if (visitedNodes.map(visitedNode => visitedNode.id()).includes(node.id())) {
    return visitedNodes;
  }

  // add visited node to collection
  visitedNodes.push(node);

  // select node
  node.select();

  // only travel through valid edges
  const edgesTo = node.outgoers(function () {
    return this.isEdge() && this.data('requiredValues').includes(requiredValue);
  });

  // break if no valid connected edges
  if (edgesTo.empty()) {
    return visitedNodes;
  }

  // travel through edges
  edgesTo.forEach(edge => {
    edge.select()
    return traverse(edge.target(), agent, visitedNodes);
  });
}

它似乎可行，但我不太擅长算法，所以我不确定这是否是构建它的聪明方法。我已经阅读了一些关于广度优先和深度优先搜索算法的内容，但我不确定我是否需要这些算法。

不使用递归是否可以遍历树？我也尝试过使用 while 循环，但由于它是一棵树，我认为我不能只使用

node = rootNode;

while (true) {
  // find leaving edges
  ...

  edgesTo.forEach(edge => {
    // set new node to traverse
    node = edge.target;
  }
}

因为我猜 edgesTo.forEach() 将在 while 循环中进行下一次迭代之前完成。我需要它“同时”遍历不同的分支。

我可以从http://js.cytoscape.org/#collection/algorithms看到该库有多种算法(包括 bfs 和 dfs)，但是当我想遍历树而不是为了搜索某个特定节点时，是否需要这些算法？

Answer 1

BFS 和 DFS 是通用的图遍历算法。它们不仅用于搜索某些特定节点。许多算法都有 BFS 和 DFS 作为子程序。

您的代码基本上是在图形上执行 DFS。您将忽略所有不需要的边并以深度优先的方式遍历图形的其余部分。

是的，可以同时使用 DFS 和 BFS 并且只使用一些特定的边来遍历图形而无需递归。您只需忽略不需要的边缘。

BFS :

Breadth-First-Search(Graph, root):
     create empty queue Q       
     visited.put(root)
     Q.enqueue(root)                      
     while Q is not empty:             
        current = Q.dequeue()     
        for each edge that edge.startpoint == current:
             if current has required value AND edge.endpoint is not in visited:
                 Q.enqueue(edge.endpoint)
                 visited.put(edge.endpoint)

DFS :

procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty:
          v = S.pop()
          if v is not labeled as discovered:
              label v as discovered
              for all edges from v to w in G.adjacentEdges(v) :
                  if edge has required value:
                       S.push(w)