Алгоритмы обхода направленного циклического графа (JavaScript) - PullRequest
Новая
       48

Алгоритмы обхода направленного циклического графа (JavaScript)

3 голосов
/ 08 июля 2010

У меня есть связанный, направленный, циклический граф. Задача состоит в том, чтобы обнаружить каждый отдельный узел в графе, не попадая в бесконечный цикл, как это сделает обычный алгоритм обхода дерева.

Можно предположить, что я уже знаю, с какого узла начинать, чтобы достичь всех точек в ориентированном графе, и что для каждого узла у меня есть функция, которая будет возвращать узлы, на которые он направляет. Известен ли алгоритм поиска всех узлов?

Основная проблема - избегать циклов, и я был бы рад, если бы был способ сделать это без отслеживания каждого отдельного узла и сравнения его со списком узлов, которые уже были пройдены.

Если вам нужны дополнительные сведения, реальная задача состоит в том, чтобы получить список всех именованных функций в 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);

Проблема с этим кодом в том, что он застревает в циклах.

Ответы [ 2 ]

5 голосов
/ 08 июля 2010

Мне бы понравилось, если бы был способ сделать это, не отслеживая каждый отдельный узел и не сравнивая его со списком уже пройденных узлов.

Это можетне так плохо, как проверка списка уже пройденных узлов.Вместо этого вы могли бы дать каждому узлу уникальный идентификатор некоторого вида: 

// psuedo
id=0;
for each node
    node.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.
0 голосов
/ 08 июля 2010

Вам необходимо вести список уже посещенных узлов, если вы хотите избежать циклов.

Например, 

__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.
...