使用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)

Answer 2

我将把我的回答归结为你明确或含蓄地提出的几个问题:

一般的BFS和DFS算法

BFS和DFS是遍历连通图(或图的连接组件)的算法。都允许您访问连接节点从一个特定的节点开始(他们不寻找一个特定节点时暗示,尽管他们可以以这样一种方式),以及他们不同的顺序遍历图(Breadth-Frist,这意味着所有的直接邻居节点之前访问了进入下一层的邻居,与深度优先相比,意义追求的一个分支,始于一个立即的邻居会更深,在继续到下一个分支之前，访问通过该特定邻居节点连接到开始节点的所有节点，这些节点是通过下一个直接邻居连接的所有节点)。

与你方要求相关的BFS和DFS

和前面一样，两种算法都访问图的连通组件中的所有节点(从起始节点通过遍历边可以到达的所有节点)。由于您有不同的需求(仅使用特定值的边进行遍历)，我建议您实现自己对任一算法的更改，并添加此需求。你实际上已经这样做了:你的算法在某种意义上是DFS的后代/版本。

BFS、DFS和递归

BFS通常不包含递归，并使用数据结构(队列)来实现其遍历顺序。

DFS很容易通过递归实现(您实现算法的直观方式与此非常相似)。但是您可以在没有递归的情况下实现DFS—使用数据结构(堆栈)来实现其遍历顺序(本质上递归隐式地使用调用堆栈作为数据结构，因此没有什么不同，尽管递归有更多的开销来处理函数调用及其环境)。您可以在DFS的wiki中看到伪代码。这里是为了方便:

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 3

Cytoscape包含许多开箱即用的常见图论算法。这些算法甚至允许您指定要包含/调用哪些元素。

你可以使用底层遍历api(如.outgoers())自己重新实现BFS遍历算法，但为什么要重新发明轮子呢?

BFS和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()以满足允许遍历元素的标准。

如果目标节点具有特定的条件，当满足这些条件时，在visit()中返回true。