LexBFS - Implementierung und Erklärung

[Max M. (Firma: Schule) (man_nam)]

Hi Leute,
Ich muss LexBFS implementieren und verstehen. Das ist ein 
Graphalgorithmus, welcher häufig verwendet wird, um Graphenklassen zu 
erkennen.
Was LexBFS macht, habe ich verstanden, jedoch nicht, wie er 
funktioniert. Er sortiert die Knoten in einem Graphen wie es auch 
BFS(=Breitensuche) tun würde.
Kann mir einer, der Ahnung hat erklären, wie es funktioniert. Im 
Internet finde ich keine Anfänger-Erklärung.
MfG
man_nam

[Axel S. (a-za-z0-9)]

Ich finde den englischen Wikipedia-Artikel gut verständlich. Ein Problem 
bei der Implementierung des Algorithmus könnte sein, daß er 
fortgeschrittene Datenstrukturen wie Mengen verwendet. Bist du denn frei 
in der Wahl der Programmiersprache? Denn es wäre sicher hilfreich, eine 
programmiersprache zu verwenden, die die benötigten Datenstrukturen von 
Haus aus bereitstellt.

Ansonsten kann dir keiner das Verstehen des Algorithmus abnehmen. 
Womöglich hilft es aber, sich einfach mal mehrere Darstellungen 
durchzulesen. Und dann kann man natürlich auch Minimalbeispiele mit 
Papier und Bleistift durchspielen.


XL