Implementación de grafos en Java
Recorrida
DFS - Por vertice
Procedimiento DFS (vertice v)
Comienzo
- Marcar v como visitado
- Para cada w adyacente a v
- Si w no está marcado
- => DFS (w)
- fin para
Fin
Código (matriz de adyacencias)
Interface
import grafos.Lista;
public interface IGrafo {
/** Pre: v no pertenece al grafo.
* 0<v<=capacidad grafo
* Post: Agrega el vértice v al grafo
*/
public void agregarVertice(int v);
/**
* Pre: origen y destino son los índices de vértices ya ingresados en el grafo
* Post: Agrega la arista origen-destino de peso "peso" en el grafo
*/
public void agregarArista(int origen, int destino, int peso);
/**
* Pre: El vértice v existe en el grafo
* Post: Elimina el vértice y todas las aristas a las que pertenezca
*/
public void eliminarVertice(int v);
/**
* Pre: La arista origen - destino existe en el grafo
* Post: Elimina la arista origen - destino
*/
public void eliminarArista(int origen, int destino);
/**
* Pre: El vértice v existe en el grafo
* Post: Retorna una lista con los vértices adyacentes de v.
* Si v no tiene adyacentes retorna la lista vacía
*/
public Lista verticesAdyacentes(int v);
/**
* Pre: a y b son vértices del grafo
* Post: Retorna true sii los vértices a y b son adyacentes.
*/
public boolean sonAdyacentes(int a, int b);
/**
* Post: Retorna true sii el vértice fue ingresado al grafo
*/
public boolean estaVertice (int v);
/**
* Post: Retorna true sii el grafo esta vacío
*/
public boolean esVacio();
public void recorridaDFS();
}
Implementación mediante uso de Matriz de adyacencias
Clase Arco (modela un arista dentro del grafo)
public class Arco{
boolean existe;
int peso;
public Arco(){
this.existe = true;
this.peso = 0;
}
public Arco(int peso){
this.existe = true;
this.peso = peso;
}
}
Clase GrafoMatriz (modela una matriz con todas las adyacencias existentes en el presente grafo)
public class GrafoMatriz implements IGrafo{
int size;
int cantNodos;
Arco[][] matrizAdyacencia;
boolean[] nodosUsados;
}
Clase GrafoLista (modela una lista con todos los nodos y a su vez con todas las adyacencias existentes en el presente grafo desde cada nodo)
ListaAdy en este caso es una lista común donde lo único que guarda es el nodo al cual se vincula el que lo contiene.
public class GrafoLista implements IGrafo{
int size;
int cantNodos;
ListaAdy[] listaAdyacencia;
boolean[] nodosUsados;
}
