Graphenalgorithmen

Markieren von Knoten

 aufwärts

In vielen Graphenalgorithmen 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 Graphenalgorithmen wie Berechnung der Zusammenhangskomponenten

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 17.09.2012   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik