Graphenalgorithmen

Markieren von Knoten

In vielen Graphen­algorithmen werden die Knoten des Graphen mit Markierungen versehen. Als Knotenmenge eines Graphen verwenden wir die Menge {0, ..., n-1}. Um die Knoten des Graphen zu markieren, genügt es somit, die Elemente der Menge {0, ..., n-1} zu markieren.

Implementierung

Die Markierungen sind zunächst von unbestimmtem Typ; entsprechend versehen wir die Klasse Marker mit einem Typ-Parameter Type. Da es in Java keine Arrays mit Typ-Parameter gibt, verwenden wir stattdessen eine ArrayList mit dem entsprechenden Typ-Parameter. Der einfachste Fall ist die Markierung mit true oder false; hierfür leiten wir eine Klasse BooleanMarker von der Klasse Marker ab.

 

public class Marker<Type>
{
    private int n;
    public final Type unmarked;   // Spezialwert für "nicht markiert"
    private ArrayList<Type> mark;

    // Markierungen für n Knoten, Initialisierung mit unmarked
    public Marker(int n_, Type unmarked_)
    {
        n=n_;
        unmarked=unmarked_;
        mark=new ArrayList<Type>(n);
        for (int i=0; i<n; i++)
            mark.add(unmarked);
    }

    public void setMark(int i, Type t)
    {
        mark.set(i, t);
    }

    public Type getMark(int i)
    {
        return mark.get(i);
    }

    public void unmark(int i)
    {
        setMark(i, unmarked);
    }

    public void clear()
    {
        for (int i=0; i<n; i++)
            unmark(i);
    }

    public boolean isMarked(int i)
    {
        return !getMark(i).equals(unmarked);
    }

    @Override
    public String toString()
    {
        String s="";
        for (int i=0; i<n; i++)
            s+=getMark(i)+" ";
        return s;
    }

} // end class Marker

 

Für den einfachen Fall eines Markers mit Typ-Parameter Boolean steht die Klasse BooleanMarker zur Verfügung.

public class BooleanMarker extends Marker<Boolean>
{
    public BooleanMarker(int n_)
    {
        super(n_, false);
    }

    public void mark(int i)
    {
        setMark(i, true);
    }

}

 

Beispiele für die Verwendung von Markern finden sich in Graphen­algorithmen wie Berechnung der Zusammenhangs­komponenten

 

Weiter mit:   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 17.09.2012   Updated: 20.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden