LexBFS - Implementierung und Erklärung

OP (Firma: Schule) #3569384
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
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

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 12 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.