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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了有向循环图遍历的算法(JavaScript)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1803字，纯文字阅读大概需要3分钟。

内容图文

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

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

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

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

内容总结

以上是互联网集市为您收集整理的有向循环图遍历的算法(JavaScript)全部内容，希望文章能够帮你解决有向循环图遍历的算法(JavaScript)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端