有向循环图遍历算法（JavaScript） [英] Algorithms for Directed Cyclic Graph Traversal (JavaScript)

问题描述

我有一个连接的，定向的循环图。任务是发现图中的每一个节点，而不会陷入无限循环，因为常规的树遍历算法会做。

你可以假设我已经知道了什么节点开始以便到达有向图中的所有点，并且对于每个节点，我有一个函数将返回它指向的节点。是否有已知的算法来查找所有节点？

主要问题是真的避免周期，如果有一种方法可以做到这一点，每个节点并将其与已经遍历的节点列表进行比较。

如果您需要更多细节，实际任务是获取每个命名函数的列表在JavaScript中，包括其他对象属性的函数。所以我尝试了类似下面的内容，因为我认为JS对象的对象引用了一棵树（但当然不是）：

 函数__findFunctions（obj）{
 for（var f in obj）{
 //对于带自己的边的特例
 if（obj === obj [f ]）{
 continue 
} 
 if（typeof obj [f] ==='function'&& 
 obj.hasOwnProperty（f）&& 
 //排除原生函数，我们只希望用户定义的
！（/ \ [（native \scode | object \sfunction）\] / i）.test（obj [f]。 toString（））&& 
 //用__前缀排除函数
！（/ ^ \s * function \s * __ /）。test（obj [f] .toString（） ）
 document.write（f +< br />+ obj [f] .toString（）+< hr />）; 
} 
 // alert（typeof obj [f] +\\\
+ obj +\\\
+ obj [f] +\\\
+ f）
 __findFunctions（OBJ [F]）; 
} 
} 
 __findFunctions（window）; 
  

这段代码的问题在于它会陷入循环。

我会喜欢它，如果有一种方法可以做到这一点，而不需要跟踪每个节点并将它与一个列表进行比较已经被遍历的节点。

它可能不如检查已遍历节点的列表那么糟糕。你可以给每个节点一个唯一的ID：
为每个节点
node.id = id ++;

etc。

然后您可以添加当您遍历时，每个节点的ID都是一个散列值：

  var alreadyTraversed = {}; 
 
 //遍历节点：$ b​​ $ b alreadyTraversed [node.id] = true; 
  

稍后，当您需要检查它是否已遍历时：

  if（node.id in alreadyTraversed）//它已经被遍历... 
  

---

或者，对于一个非常简单的解决方案，只需在每个对象上设置一些属性即可：

  node._traversed = true; 
 
 //稍后：
 if（someNode._traversed）//已遍历。 
  

I have a connected, directed, cyclic graph. The task is to discover every single node in the graph without falling into an infinite loop, as a regular tree traversal algorithm will do.

You can assume that I already know what node to start at so as to reach all points in the directed graph, and that for each node I have a function that will return the nodes it directs to. Is there a known algorithm for finding all nodes?

The main issue is really avoiding cycles, and I would love it if there was a way to do that without keeping track of every single node and comparing it with a list of nodes that has already been traversed.

If you need more details, the actual task is to get a list of every named function in JavaScript, including functions that are properties of other objects. So I tried something like the following, as I thought the JS objects' references to each other made a tree (but of course it doesn't):

function __findFunctions(obj){
  for (var f in obj){
    // for special case of edge with self
    if (obj === obj[f]){
      continue
    }
    if (typeof obj[f] === 'function' &&
        obj.hasOwnProperty(f) &&
          // exclude native functions, we only want user-defined ones
        !(/\[(native\scode|object\sfunction)\]/i).test(obj[f].toString()) &&
          // exclude functions with __ prefix
        !(/^\s*function\s*__/).test(obj[f].toString())
       ){
      document.write(f + "<br/>" + obj[f].toString() + "<hr/>");
    }
    //alert(typeof obj[f] + "\n" + obj + "\n" + obj[f] + "\n" + f)
    __findFunctions(obj[f]);
  }
}
__findFunctions(window);

The problem with this code is that it gets stuck in cycles.

解决方案

I would love it if there was a way to do that without keeping track of every single node and comparing it with a list of nodes that has already been traversed.

It may not be as bad as checking a list of already-traversed nodes. You could, instead, give each node a unique ID of some sort:

// psuedo
id=0;
for each node
    node.id = id++;

etc.

Then you can add each node's ID to a hash while you traverse:

var alreadyTraversed = {};

// Traversing a node:
alreadyTraversed[node.id] = true;

And later on, when you need to check whether or not its already been traversed:

if (node.id in alreadyTraversed) // It's already been traversed...

---

Or, for a really rudimentary solution, simply set some property on each object that you traverse:

node._traversed = true;

// Later:
if (someNode._traversed) // already traversed.

这篇关于有向循环图遍历算法（JavaScript）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！