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:
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:
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];
}
}