Strategien zum Graphdurchlauf

Ziel des Graphendurchlauf ist es, alle Knoten eines Graphen nach einer festgelegten Strategie zu besuchen. Das Besuchen steht dabei stellvertretend für die Verarbeitung des Knotens, in den folgenden Quellcode-Beispielen wird z.B. lediglich die ID des aktuelle besuchten Knotens ausgedruckt.

Beim Durchlauf von Graphen kommen analog zu Bäumen wieder die beiden Strategien der Tiefensuche und der Breitensuche in Betracht. Die Tiefensuche kann entweder rekursiv oder mithilfe eines Stacks umgesetzt werden. Um die Analogie zur Breitensuche herausarbeiten zu können, wird an dieser Stelle ein Stack verwendet. Das im nächsten Abschnitt beschriebene Backtracking, das auf der Tiefensuche basiert, wird dagegen vollständig rekursiv realisiert.

Tiefensuche

Zentrales Hilfsmittel der Tiefensuche ist ein Stack. Er sorgt dafür, dass ausgehend vom aktuellen Knoten immer der letzte Nachbar weiter verfolgt wird. (Bemerkung: Die Festlegung auf den letzten Nachbarn wurde hier willkürlich getroffen. Da es keine Anordnung von Nachbarknoten gibt, hat diese Festlegung keine Auswirkung auf die Funktionsfähigkeit des Verfahrens, sondern lediglich auf die Reihenfolge der besuchten Knoten.)

Zu Beginn wird der Startknoten auf den Stack gelegt, anschließend alle seine noch nicht besuchten Nachbarn. Da nun der oberste Knoten vom Stack genommen und weiter verarbeitet wird, geht die Verarbeitung also mit dem zuletzt auf den Stack gelegten Nachbarknoten weiter.

public void sucheTief(Graph g, String startid) {

    g.setAllVertexMarks(false);

    Vertex startnode = g.getVertex(startid);          
    Stack<Vertex> s = new Stack<Vertex>();
    s.push(startnode);

    while (!s.isEmpty()) {

        Vertex aktuell = (Vertex) s.top();
        if (!aktuell.isMarked()) { // VERARBEITEN
            System.out.println(aktuell.getID()); 
        }
        aktuell.setMark(true);

        List<Vertex> l = g.getNeighbours(aktuell);
        l.toFirst();
        boolean gefunden = false;

        while (l.hasAccess()) { // nicht-markieter Knoten vorhanden?
            Vertex nachbar = l.getContent();
            if (!nachbar.isMarked()) {
                s.push(nachbar);
                gefunden = true;
                break;
            }
            else {
                l.next();
            }
        }

        if (!gefunden) { s.pop(); }

    }
}

Breitensuche

Im Unterschied zur Tiefensuche wird bei der Breitensuche eine Schlange als Hilfsdatenstruktur eingesetzt. Da für jeden aktuellen alle noch nicht besuchten Nachbarn an die Schlange angehängt werden, ergibt sich eine "ebenenweise" Abarbeitung des Graphen.

public void sucheBreit(Graph g, String startid) {

    g.setAllVertexMarks(false);   

    Vertex startnode = g.getVertex(startid);
    Queue<Vertex> q = new Queue<Vertex>();
    q.enqueue(startnode);

    while (!q.isEmpty()) {

        Vertex aktuell = q.front();
        if (!aktuell.isMarked()) { // VERARBEITEN
            System.out.println(aktuell.getID()); 
        }
        aktuell.setMark(true);

        q.dequeue();

        List<Vertex> l = g.getNeighbours(aktuell);
        l.toFirst();

        while (l.hasAccess()) {
            Vertex nachbar = l.getContent();
            if (!nachbar.isMarked()) { // nicht doppelt in die Queue
                q = nichtDoppeltEinfuegen(q, nachbar);
            }
            l.next();
        }

    }
}

Die Hilfsmethode, die das nicht-doppelte Einfügen in die Schlange realisiert, sei hier der Vollständigkeit halber mit angegeben:

private Queue<Vertex> nichtDoppeltEinfuegen(Queue<Vertex> q, Vertex node) {

    Queue<Vertex> qneu = new Queue<Vertex>();
    boolean insert = true;

    while (!q.isEmpty()) {
        Vertex n = q.front();
        q.dequeue();
        if (n.getID().equals(node.getID())) {
            insert = false;
        }
        qneu.enqueue(n);
    }

    if (insert) { qneu.enqueue(node); }

    return qneu;
}

results matching ""

    No results matching ""