使用 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 循环中的下一个迭代之前完成。我需要它遍历 'simultaneously' 不同的分支。

我从http://js.cytoscape.org/#collection/algorithms看到这个库有多种算法（包括bfs和dfs），但是当我想遍历树而不是为了搜索一个特定的节点时，我需要那些算法吗？

Answer 1

我将把我的回答缩减为您明确或隐含提出的几个问题：

一般的 BFS 和 DFS 算法

BFS 和 DFS 是遍历连通图（或图的连通分量）的算法。它们允许您从特定的起始节点访问所有连接的节点（它们不会像您暗示的那样搜索特定的节点，尽管它们可以以这种方式使用），并且不同按照它们遍历图的顺序（Breadth-Frist，意味着在进入下一层邻居之前访问一个节点的所有直接邻居，与 Depth-First 相比，意味着首先从一个直接邻居开始的分支并更深入，在继续下一个分支之前访问通过该特定邻居节点连接到起始节点的所有节点，这些节点是通过下一个直接邻居连接的所有节点）。

与您的要求相关的 BFS 和 DFS

和以前一样，这两种算法都会访问图中连通分量中的所有节点（通过遍历边从起始节点可以到达的所有节点）。由于您有不同的要求（仅使用特定值的边缘遍历），我建议您实现自己对任一算法的更改，添加此需求。你实际上已经做到了：你的算法在某种意义上是 DFS 的 descendant/version。

BFS 和 DFS 以及递归

BFS does not normally include recursion 并使用数据结构（队列）来实现其遍历顺序。

DFS 很容易通过递归实现（并且您实现算法的直观方式与此非常相似）。但是你可以在没有递归的情况下实现 DFS - 使用数据结构（堆栈）来实现它的遍历顺序（本质上递归使用调用堆栈作为数据结构隐式所以它没有什么不同，虽然递归有更多的开销来处理与函数调用及其环境）。您可以在 wiki of 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) do
              S.push(w)

Answer 2

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)

Answer 3

Cytoscape 包括许多 common graph theory algorithms 开箱即用的工具。这些算法甚至允许您指定要包含/调用哪些元素。

您可以使用像.outgoers()这样的低级遍历API自己重新实现BFS遍历算法，但为什么要重新发明轮子？

BFS and DFS 内置于 Cytoscape 中：

cy.elements().stdFilter(function( ele ){
  return ele.isNode() ? includeThisNode( ele ) : includeThisEdge( ele ); // eles to include
}).bfs({
  visit: function(){ ... } // called when new ele visited
});

指定 includeThisNode() 和 includeThisEdge() 以满足允许遍历哪些元素的条件。

如果您有一个符合特定条件的目标节点，当满足这些条件时 return 在 visit() 中为真。

使用 while 循环迭代遍历图

Traversing graph using while loop iteration

javascript

algorithm

tree

graph-algorithm

cytoscape.js

一般的 BFS 和 DFS 算法

与您的要求相关的 BFS 和 DFS

BFS 和 DFS 以及递归