Iterador de nodos adyacentes
La operación más común en la teoría de grafos es recorrer las aristas adyacentes, atravesando las aristas relacionadas a través de un vértice. La complejidad temporal de recorrer las aristas adyacentes de una matriz de adyacencia es O(V); la lista de adyacencia puede encontrarlas directamente, con mayor eficiencia.

Iteración de la matriz de adyacencia:
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;
}
...
Iteración de la lista de adyacencia:
// Devuelve todas las aristas adyacentes de un vértice en el grafo
// Dado que Java usa el mecanismo de referencias, devolver un Vector no conlleva gastos adicionales,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
...
Para estas dos formas de representar el grafo, podemos abstraer una interfaz, generando el marco de este conjunto de algoritmos, sin tener que preocuparnos por si la capa subyacente es una lista de adyacencia o una matriz de adyacencia.
En esta sección se escribió un caso de prueba GraphReadTest, que a través de la llamada a la interfaz abstracta logra mostrar el grafo; se puede consultar en el paquete read.
* Interfaz abstracta del grafo
*/
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);
}
Código de ejemplo Java
Descarga del paquete de código fuente:Download
(1) Iteración de la matriz de adyacencia
Código del archivo src/ejemplo/graph/DenseGraphIterater.java:
import java.util.Vector;
/**
* Iteración de la matriz de adyacencia
*/
public class DenseGraphIterater {
// Número de nodos
private int n;
// Número de aristas
private int m;
// Si es un grafo dirigido
private boolean directed;
// Datos específicos del grafo
private boolean[][] g;
// Constructor
public DenseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g se inicializa como una matriz booleana de n*n, cada g[i][j] es false, lo que indica que no hay aristas
// false es el valor por defecto de las variables de tipo boolean
g = new boolean[n][n];
}
// Devuelve el número de nodos
public int V(){ return n;}
// Devuelve el número de aristas
public int E(){ return m;}
// Agrega una arista al grafo
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] = true;
if( !directed )
g[w][v] = true;
m ++;
}
// Verifica si hay una arista de v a w en el grafo
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
// Devuelve todas las aristas adyacentes de un vértice en el grafo
// Dado que Java usa el mecanismo de referencias, devolver un Vector no conlleva gastos adicionales,
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) Iteración de la lista de adyacencia
Código del archivo src/ejemplo/graph/SparseGraphIterater.java:
import java.util.Vector;
/**
* Iteración de la lista de adyacencia
*/
public class SparseGraphIterater {
private int n; // Número de nodos
private int m; // Número de aristas
private boolean directed; // Si es un grafo dirigido
private Vector<Integer>[] g; // Datos específicos del grafo
// Constructor
public SparseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // Inicializa sin ninguna arista
this.directed = directed;
// g se inicializa como n vectores vacíos, lo que significa que cada g[i] está vacío, es decir, no hay aristas
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
public int V(){ return n;} // Devuelve el número de nodos
public int E(){ return m;} // Devuelve el número de aristas
// Agrega una arista al grafo
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
m ++;
}
// Verifica si hay una arista de v a w en el grafo
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;
}
// Devuelve todas las aristas adyacentes de un vértice en el grafo
// Dado que Java usa el mecanismo de referencias, devolver un Vector no conlleva gastos adicionales,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}