有向循环图遍历的算法(JavaScript)

Question

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

您可以假设我已经知道要启动哪个节点以便到达有向图中的所有点,并且对于每个节点,我有一个函数将返回它指向的节点.是否有已知的查找所有节点的算法？

主要问题是避免循环,如果有办法在不跟踪每个节点并将其与已遍历的节点列表进行比较的情况下,我会喜欢它.

如果您需要更多详细信息,实际任务是获取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);

这段代码的问题在于它会在周期中陷入困境.

Answer 1

如果有办法在不跟踪每个节点并将其与已经遍历的节点列表进行比较的情况下,我会喜欢它.

它可能没有检查已经遍历的节点列表那么糟糕.相反,您可以为每个节点提供某种类型的唯一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.