A continuación dejo el TAD(Tipo abstracto de datos) genérico o interface en Java de un grafo dirigido y la implementación con colecciones y una matriz de costos.
public interface Grafo <E>{
//Modificadoras
void insVertice(E dato);
void insArco(int o, int d,int dato) throws LimiteException ;
void elimArco(int o, int d)throws LimiteException ;
//Analizadoras
int costoArco(int x, int y)throws LimiteException ;
List<E> sucesores(int v)throws LimiteException ;
E infoVertice(int v)throws LimiteException ;
int ordenGrafo();
int inf=999999;
}
public class GrafoCol<E> implements Grafo<E> {
List<E> vertices;
int aristas [][];
public GrafoCol()
{
vertices = new ArrayList<>();
aristas = new int[100][100];
for (int i = 0; i < aristas.length; i++) {
for (int j = 0; j < aristas.length; j++) {
if(i!=j)
aristas[i][j] = inf;
//De resto se llena automáticamente de ceros(en este caso la diag ppal)
}
}
}
@Override
public void insVertice(E dato) {
vertices.add(dato);
}
@Override
public void insArco(int o, int d, int dato) throws LimiteException {
if(o>= ordenGrafo() || d>= ordenGrafo())
throw new LimiteException("Te pasaste");
aristas[o][d] = dato;
}
@Override
public void elimArco(int o, int d) throws LimiteException {
if(o>= ordenGrafo() || d>= ordenGrafo())
throw new LimiteException("Te pasaste");
aristas[o][d] = inf;
}
@Override
public int costoArco(int x, int y) throws LimiteException {
if(x>= ordenGrafo() || y>= ordenGrafo())
throw new LimiteException("Te pasaste");
return aristas[x][y];
}
@Override
public List<E> sucesores(int v) throws LimiteException {
List<E> res = new ArrayList<>();
if(v>= ordenGrafo())
throw new LimiteException("WHY");
for (int i = 0; i < ordenGrafo(); i++) {
if(i!=v && aristas[v][i]!= inf)
res.add(infoVertice(i ));
}
return res;
}
@Override
public E infoVertice(int v) throws LimiteException {
return vertices.get(v);
}
@Override
public int ordenGrafo() {
return vertices.size();
}
}
public class LimiteException extends Exception {
public LimiteException(String msg)
{
super(msg);
}
}