Iterator für benachbarte Knoten

Die häufigste Operation in der Graphentheorie ist das Durchlaufen benachbarter Kanten, wobei ein Knoten verwendet wird, um die zugehörigen benachbarten Kanten zu durchlaufen. Die Zeitkomplexität beim Durchlaufen benachbarter Kanten in einer Adjazenzmatrix beträgt O(V), während eine Adjazenzliste sie direkt finden kann, was effizienter ist.

Adjazenzmatrix-Iteration:

...
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    Vector<Integer> adjV = new Vector<Integer>();
    for(int i = 0 ; i < n ; i ++ )
        if( g[v][i] )
            adjV.add(i);
    return adjV;
}
...

Adjazenzlisten-Iteration:

...
// Alle benachbarten Kanten eines Knotens im Graphen zurückgeben
// Da Java einen Referenzmechanismus verwendet, verursacht die Rückgabe eines Vector keinen zusätzlichen Overhead,
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    return g[v];
}
...

Für diese beiden Methoden der Graphendarstellung können wir eine Schnittstelle abstrahieren, um das Gerüst dieser Algorithmensammlung zu erzeugen, ohne berücksichtigen zu müssen, ob die darunterliegende Schicht eine Adjazenzliste oder eine Adjazenzmatrix ist.

In diesem Abschnitt wird ein Testfall GraphReadTest geschrieben, der die Graphanzeige durch Aufruf der abstrakten Schnittstelle implementiert und im Paket read eingesehen werden kann.

/**
* Abstrakte Schnittstelle des Graphen
 */

public interface Graph {
    public int V();
    public int E();
    public void addEdge( int v , int w );
    boolean hasEdge( int v , int w );
    void show();
    public Iterable<Integer> adj(int v);
}

Java-Beispielcode

Quellcode-Paket-Download:Download

(1) Adjazenzmatrix-Iteration

Code der Datei src/example/graph/DenseGraphIterater.java:

package example.graph;

import java.util.Vector;

/**
* Adjazenzmatrix-Iteration
 */

public class DenseGraphIterater {
    // Knotenanzahl
    private int n;
    // Kantenanzahl
    private int m;
    // Gibt an, ob es ein gerichteter Graph ist
    private boolean directed;
    // Spezifische Daten des Graphen
    private boolean[][] g;

    // Konstruktor
    public DenseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // g wird als eine n*n boolesche Matrix initialisiert, wobei jedes g[i][j] false ist, was anzeigt, dass keine Kanten vorhanden sind
        // false ist der Standardwert für boolesche Variablen
        g = new boolean[n][n];
    }
    // Gibt die Anzahl der Knoten zurück
    public int V(){ return n;}
    // Gibt die Anzahl der Kanten zurück
    public int E(){ return m;}

    // Fügt eine Kante zum Graphen hinzu
    public void addEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        if( hasEdge( v , w ) )
            return;
        g[v][w] = wahr;
        if( !directed )
            g[w][v] = wahr;
        m ++;
    }

    // Prüft, ob eine Kante von v nach w im Graphen vorhanden ist
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
    // Alle benachbarten Kanten eines Knotens im Graphen zurückgeben
    // Da Java einen Referenzmechanismus verwendet, verursacht die Rückgabe eines Vector keinen zusätzlichen Overhead,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        Vector<Integer> adjV = new Vector<Integer>();
        for(int i = 0 ; i < n ; i ++ )
            if( g[v][i] )
                adjV.add(i);
        return adjV;
    }
}

(2) Iteration über Adjazenzliste

src/example/graph/SparseGraphIterater.java Datei-Code:

package example.graph;

import java.util.Vector;

/**
* Iteration über Adjazenzliste
 */

public class SparseGraphIterater {

    private int n;  // Knotenanzahl
    private int m;  // Kantenanzahl
    private boolean directed;    // Ob es ein gerichteter Graph ist
    private Vector<Integer>[] g; // Konkrete Daten des Graphen

    // Konstruktor
    public SparseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // Initialisieren ohne Kanten
        this.directed = directed;
        // g wird als n leere Vektoren initialisiert, was bedeutet, dass jedes g[i] leer ist, d. h. keine Kanten.
        g = (Vector<Integer>[])new Vektor[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }
    public int V(){ return n;} // Gibt die Anzahl der Knoten zurück
    public int E(){ return m;} // Gibt die Anzahl der Kanten zurück

    // Fügt eine Kante zum Graphen hinzu
    public void addEdge( int v, int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        g[v].hinzufügen(w);
        if( v != w && !directed )
            g[w].hinzufügen(v);

        m ++;
    }

    // Prüft, ob eine Kante von v nach w im Graphen vorhanden ist
    boolean hasEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v].elementAt(i) == w )
                return true;
        return false;
    }

    // Alle benachbarten Kanten eines Knotens im Graphen zurückgeben
    // Da Java einen Referenzmechanismus verwendet, verursacht die Rückgabe eines Vector keinen zusätzlichen Overhead,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
}
Weitere Erweiterungen