Algorithmes pour la traversée de graphe cyclique dirigée (JavaScript)

Question

J'ai un graphe cyclique orienté et connecté. La tâche consiste à découvrir chaque noeud du graphe sans tomber dans une boucle infinie, comme le fera un algorithme de traversée d'arbres.

Vous pouvez supposer que je sais déjà à quel nœud commencer pour atteindre tous les points dans le graphe orienté, et que pour chaque nœud j'ai une fonction qui retournera les nœuds qu'il dirige vers. Existe-t-il un algorithme connu pour trouver tous les nœuds?

Le problème principal est vraiment d'éviter les cycles, et j'adorerais qu'il y ait un moyen de le faire sans garder trace de chaque nœud et de le comparer avec une liste de nœuds qui ont déjà été traversés.

Si vous avez besoin de plus de détails, la tâche actuelle consiste à obtenir une liste de toutes les fonctions nommées en JavaScript, y compris les fonctions qui sont des propriétés d'autres objets. J'ai donc essayé quelque chose comme ce qui suit, que je pensais que les références des objets JS à l'autre fait un arbre (mais bien sûr, il ne fonctionne pas):

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

Le problème avec ce code est qu'il se coince dans cycles.

Answer 1

Vous devez gérer une liste de noeuds déjà visités si vous voulez éviter les cycles.

E.g.

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

J'aimerais s'il y avait un moyen de le faire sans garder une trace de chaque nœud unique et en le comparant avec une liste de noeuds qui a déjà été parcouru.

Cela peut ne pas être aussi mauvais que de vérifier une liste de nœuds déjà traversés. Vous pouvez, au contraire, donner à chaque noeud un identifiant unique d'une sorte:

// psuedo 
id=0; 
for each node 
    node.id = id++; 

etc.

Ensuite, vous pouvez ajouter l'ID de chaque nœud à un hachage pendant que vous traversez:

var alreadyTraversed = {}; 

// Traversing a node: 
alreadyTraversed[node.id] = true; 

Et plus tard, lorsque vous devez vérifier si oui ou non son déjà été traversées:

if (node.id in alreadyTraversed) // It's already been traversed... 

---

Ou, pour une solution vraiment rudimentaire, définissez simplement une propriété sur chaque objet que vous traverserez:

node._traversed = true; 

// Later: 
if (someNode._traversed) // already traversed.