我有一个连通的,有向的循环图.任务是发现图中的每个节点,而不会陷入无限循环,就像常规的树遍历算法一样.

您可以假设我已经知道从哪个节点开始,以便到达有向图中的所有点,并且对于每个节点,我都有一个函数,该函数将返回它定向到的节点.是否存在用于查找所有节点的已知算法？

主要问题实际上是避免循环,如果有一种方法可以做到这一点,而又不跟踪每个节点并将其与已经遍历的节点列表进行比较,我会喜欢它.

如果需要更多详细信息,实际的任务是获取JavaScript中每个命名函数的列表,包括作为其他对象属性的函数.因此,我尝试了以下类似的操作,因为我认为JS对象之间的相互引用形成了一棵树(但当然不是)：

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);

此代码的问题在于它陷入了循环.

解决方法:

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.

它可能不如检查已遍历的节点列表那么糟糕.您可以改为给每个节点某种唯一的ID：

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

等等

然后,您可以在遍历时将每个节点的ID添加到哈希中：

var alreadyTraversed = {};

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

然后,当您需要检查其是否已经遍历时：

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

或者,对于真正的基本解决方案,只需在您遍历的每个对象上设置一些属性：

node._traversed = true;

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