Als Beispiel für den sinnvollen Gebrauch einer node_list wollen wir eine Möglichkeit aufzeigen, die Funktion TOPSORT() zur Berechnung einer Topologischen Sortierung eines Graphen zu implementieren.

Wir laufen einmal über alle Knoten des Graphen, merken uns die ursprünglichen Eingangsgrade und speichern alle Knoten, die Eingangsgrad 0 haben, in einer node_list namens ZEROINDEG. Solange diese Liste nicht leer ist, ziehen wir einen Knoten heraus und geben ihm die nächste Nummer in der Toplogischen Sortierung. Wir entfernen ihn (konzeptionell) aus dem Graphen, indem wir die Eingangsgrade aller benachbarten Knoten um 1 vermindern. Wird dabei der Eingangsgrad eines Knotens auf 0 gesetzt, so wird dieser Knoten nach ZEROINDEG aufgenommen. Das Verfahren endet, wenn ZEROINDEG leer ist.

Hat am Ende jeder Knoten eine (fortlaufende) Nummer erhalten, so hat der Graph eine Topologische Sortierung. Ist dagegen ZEROINDEG leer geworden, ohne dass alle Knoten eine Nummer erhalten haben, so besitzt der Graph einen Zyklus.

#include <LEDA/graph.h>
#include <LEDA/node_array.h>
#include <LEDA/node_list.h>

using leda::graph;
using leda::node_array;
using leda::node_list;
using leda::node;

bool TOPSORT(const graph& G, node_array<int>& top_num)
{
  // store all nodes with indegree = 0 in ZEROINDEG
  node_list ZEROINDEG;  
  node_array<int> INDEG(G, 0); // and count indegrees
  node v;
  forall_nodes(v, G) 
    if((INDEG[v] = G.indeg(v)) == 0) 
      ZEROINDEG.append(v);


  // while there is a node with indegree = 0, pop it and assign next
  // topological number to it
  int counter = 0 ;
  while(!ZEROINDEG.empty()) { 
    v = ZEROINDEG.pop();
    top_num[v] = ++counter;
    // decrement indegree of all adjacent nodes w
    // append w to ZEROINDEG if indegree becomes 0
    node w;
    forall_adj_nodes(w, v)
      if(--INDEG[w] == 0) 
        ZEROINDEG.append(w);
  }

  // G has a topological sorting iff all nodes have been numbered
  return counter == G.number_of_nodes();
}

Da jeder Knoten v nur einmal nach ZEROINDEG aufgenommen wird und jede Kante (v,w) nur einmal betrachtet wird, hat dieses Verfahren Laufzeit O(n+m).