有向循环图遍历算法 (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.

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.

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