Markierung von Graphen

Wenn wir in einem allgemeinen Graphen Datenelemente ablegen und wiederfinden wollen, so brauchen wir ein Durchwanderungsverfahren, um jedes Datenelement aufzufinden und genau einmal zu bearbeiten. Wenn eine Liste aller Knoten vorliegt, so ist dies einfach; öfters hat man aber nur Information über die Kanten. Da die Kanten im Prinzip ganz beliebig liegen können, haben wir zuwenig Strukturinformation, um von vorneherein sicherstellen zu können, daß jedes Datenelement gefunden und genau einmal bearbeitet wird; wir müssen uns also Informationen über den bisherigen Ablauf merken, und eine Möglichkeit dazu ist eine Markierung oder "Färbung" der bereits besuchten Knoten. Dabei ist klar, daß wir ausgehend von einem beliebigen Knoten über die Kanten nur seine Zusammenhangskomponente erreichen können; Knoten außerhalb davon müssen wir auf andere Weise suchen, und wir nehmen an, daß eine solche Möglichkeit gegeben ist.

Wir wollen jede Komponente eines Graphen mit einer eigenen Farbe markieren; dabei wird auch jeder Knoten genau einmal markiert (und kann dabei auch bearbeitet werden). 

TYPE Farbe = 1 .. fmax;

PROCEDURE markiereGraph;
VAR x: Knoten; f: Farbe;
BEGIN f := 1;
      WHILE exist(unmarkierteKnoten)
      DO x := any(unmarkierteKnoten);
         markiereKomponente(x, f);
         f := f + 1;
      END;
END markiereGraph;

PROCEDURE markiereKomponente(x: Knoten; f: Farbe);
VAR y: Knoten;
BEGIN markiereKnoten(x, f);
      FOR ALL y IN Nachbarn(x)
      DO IF NOT markiert(y) 
         THEN markiereKomponente(y, f);
         END;
      END;
END markiereKomponente;
zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36