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:

package ejemplo.graph;

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:

package ejemplo.graph;

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];
    }
}
Otras extensiones