有向循环图遍历算法（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);

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

- ehsanul

---

请忽略正则表达式，在这个问题的背景下不是太重要。不过，我很想知道是否有更好的方法来区分用户定义的函数和本地函数。 - ehsanul

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.

- James

---

很遗憾，你的伪代码不起作用，因为“对于每个节点”实际上是我要寻找的图遍历算法。然而，它确实给了我一个想法，如果JS允许的话：使用节点对象本身作为ID，而不是整数。我在Ruby中做过这种事情，我会在JS中尝试一下。谢谢！ - ehsanul

@ehsanul：请看我的第二个解决方案 :) - James

哦，太棒了。这不仅是基本的，而且是正确的解决方案。现在我可以安心睡觉，知道有一个合理的解决方案等着我醒来。 - ehsanul

你知道除了字符串以外，还有哪些 JS 对象不能拥有属性吗？ - ehsanul

空值、未定义、字符串、布尔、数字... 尽管最后三个可以有属性，但从技术上讲，它们不会保留这些属性，因为它们没有被包装（请尝试使用 new String() 代替...）。 - James

Answer 2

如果想避免循环，您需要维护一个已访问节点的列表。

例如：

__findFunctions(obj, visited) as your signature
at start do an "in array" test for current obj and return if so.
at start add obj to the visited for subsequent traversals.

- Matt Mitchell

Answer 3

这里有一个快速答案，你可以在codePen上检查一下 https://codepen.io/vjuju/pen/PoXZJQo

const cyclic_graph = new Map([
  ["a", { dependencies: ["b", "c"] }],
  ["b", { dependencies: ["d"] }],
  ["c", { dependencies: ["d"] }],
  ["d", { dependencies: ["a"]}],
  ["e", { dependencies: ["e"] }]
]);

const f = ({ node, node_name }) => {
  console.log(node_name);
};

// For cyclic graphs
// and acyclic graphs on which
// we only want to apply the function f once
// on each node
const traverse_cyclic_graph = (graph, f) => (...node_names) => {
  // We keep a state at the graph level
  let called = new Set();

  const traverse_graph = (graph, f) => (node_name) => {
    const node = graph.get(node_name);
    if (!node || called.has(node_name)) return;
    called.add(node_name);
    node.dependencies?.map(traverse_graph(graph, f));
    f({ node, node_name });
  };

  node_names.forEach(traverse_graph(graph, f));
};

const traverse_all_cyclic_graph = (graph, f) =>
  traverse_cyclic_graph(cyclic_graph, f)(...cyclic_graph.keys());

//traverse_cyclic_graph(cyclic_graph, f)("a");
traverse_all_cyclic_graph(cyclic_graph, f);

- Julien Vinckel