Traversée de graphes acycliques dirigés dans l'application Web Java

Question

Je construis donc une application web dans laquelle vous pouvez construire un graphe orienté où un noeud représentera une opération et l'arête représentera le flux de données entre ces opérations. Donc, pour un bord {u, v}, vous devez exécuter avant v. Click this link to see a sample graph

Le noeud START représente la valeur initiale et les autres noeuds sauf la sortie exécutent l'opération spécifiée. Le noeud de sortie affichera la valeur qu'il reçoit en entrée.

Quelle méthode d'algorithme dois-je utiliser pour traiter un graphique comme celui-là?

Answer 1

Ceci est un exemple parfait d'un tri topologique. L'algorithme le plus commun pour créer un ensemble en suivant les exigences de la commande via la traversée est Kahn's Algorithm. Le pseudocode peut être vu ci-dessous et les informations dans le lien Wikipedia devraient être suffisantes pour vous aider à démarrer.

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    add n to tail of L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into S 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order) 

Notez que le "noeud de départ" sera appliqué en représentant correctement les arêtes entrantes dans le graphe. Ce sera le seul noeud à S à démarrer. S'il vous plaît laissez-moi savoir dans les commentaires si vous souhaitez d'autres informations.