necesito un programa en grafos

anderpichurt
24 de Febrero del 2006
hola atodos necesito un programa en jgrasp que me calcule la minima cantidad de semestres, ya que nos dan la cantidad de matrias que suelen dar todos los semestres y sus debidos prerrequisitos, es por ello que necesito implementar un programa en grafos que me haga dicho procedimiento, agradesco su atencion y colaboracion prestada por favor respondame lo mas pronto posible.............

ortodoxo01
24 de Febrero del 2006
mira el programa que buscas no es neseciaria mente un programa sino un metodo que es el disktra (no se como se escribe ) pero que es lo que hace
calcula la cantidad minima

import java.*;
import java.io.*;
import java.lang.*;

class JGrafo
{

private JLista lista;
private JMatriz matriz;
int[] aux;
int[] d;
Object[] p;
static final int MAX=100;
static final int INFINITO=585858;
public JGrafo(){
lista=new JLista();
matriz=new JMatriz();
aux =new int[MAX];
d=new int[MAX];
p=new Object[MAX];

}
public void incertar_arista_dirigida(Object vertice1, Object vertice2, float peso)throws Exception{
int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertice2);
if((x!=-1)&&(y!=-1)){
matriz.incertar_camino_dirigido(x-1,y-1,peso);

}
else{
throw new Exception();
}
}
public void incertar_vertice(Object nombre){
if((lista.longitud())==(matriz.cord))
{
matriz.redimencionar();
lista.adicionar(nombre);
}
else{

lista.adicionar(nombre);
}

}

public void eliminar_vertice(Object nombre)throws Exception{

int cor;
cor = lista.busqueda(nombre);
if (cor !=-1){
try{
matriz.eliminar_vertice(cor-1);
lista.eliminar(cor);
}
catch(Exception e){throw new Exception();}
}
else{
throw new Exception();
}

}

public void eliminar_arista(Object vertice1, Object vertice2)throws Exception{
int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertice2);
if((x!=-1)&&(y!=-1))
{
matriz.eliminar_camino(x-1,y-1);
}
else{
throw new Exception();

}

}

public void incertar_arista(Object vertice1, Object vertice2,float peso)throws Exception{
int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertice2);
if ((x!=-1)&&(y!=-1)){
matriz.incertar_camino(x-1,y-1,peso);
}
else{
throw new Exception();
}
}

public Object vertice(int x)throws Exception{
Object nombre;
try
{
nombre=lista.nombre(x);
return nombre;
}
catch(Exception e){throw new Exception();}
}

//este metodo da vateo
public int Cantidad_de_caminos(){
int can=0;
can=matriz.cantidad_de_camino();
return can;
}
//metodos nuevos
public int cantidad_de_vertices(){
return lista.longitud();
}
//este nmetodo pincha
public Object[] lista_de_vertises() throws Exception
{

if(!lista.vacia())
{
Object[] listado=new Object[lista.longitud()];
for(int i=0; i<lista.longitud();i++)
{ try{
listado[i]=lista.nombre(i+1);
}
catch(Exception e){throw new Exception();}
}
return listado;
}
else
{
throw new Exception();

}


}

//este metodo pincha
public float devolver_valor_camino(int x, int y){
return matriz.debolver_camino(x,y);
}
// no lo he probado
public boolean existe_camino(Object vertice1, Object vertce2){

int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertce2);
float z=matriz.debolver_camino(x,y);
if(z!=0){
return true;
}
else
{
return false;
}

}

//metododo pincha
public void Disktra(Object vertce)throws Exception
{
try
{
int posU = lista.busqueda(vertce);
JLista marcados=new JLista();
JLista resto=new JLista();
int L=lista.longitud();
for(int i=1; i<=L; i++)
{
resto.adicionar(lista.nombre(i));
}

for (int i=1; i<=L; i++)
{
d[i-1]=(int)Peso(vertce,lista.nombre(i));
p[i-1]=vertce;
}
d[posU-1]=0;
marcados.adicionar(vertce);
resto.eliminar(posU);
while(marcados.longitud()<lista.longitud())
{
int menor=INFINITO;
int posMenor=0;
L=resto.longitud();

for (int i=1; i<=L; i++)
{
Object act=new Object();
act=resto.nombre(i);
int tmpAct=lista.busqueda(act);
if (d[tmpAct-1]<menor)
{
menor=d[tmpAct-1];
posMenor=tmpAct;


}
}
Object vertMarc=new Object();
vertMarc=lista.nombre(posMenor);
marcados.adicionar(vertMarc);
resto.eliminar(resto.busqueda(vertMarc));
L=resto.longitud();
for (int i=1; i<=L; i++)
{
int tmpMar=lista.busqueda(vertMarc);
Object act=resto.nombre(i);
int tmpAct=lista.busqueda(act);
if(d[tmpAct-1]>d[tmpMar-1]+(int)Peso(vertMarc,act))
{
d[tmpAct-1]=d[tmpMar-1]+(int)Peso(vertMarc,act);
p[tmpAct-1]=vertMarc;
}
}
}
}
catch(Exception e){throw new Exception();}

}



//este metodod pincha
public void modificar(int pos,Object nombre)throws Exception{
try{
lista.modificar(pos,nombre);
}
catch(Exception e){throw new Exception();
}
}

//este metodo pincha
public float Peso(Object vertice1, Object vertice2)throws Exception{
int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertice2);
if((x!=-1)&&(y!=-1)){
return matriz.debolver_camino(x-1,y-1);
}
else{
throw new Exception();
}
}

public int longitud_del_camino_minimo(Object vertice1, Object vertice2)throws Exception{

int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertice2);
if ((x!=-1) &&(y!=-1))
{
try{
Disktra(vertice1);
return d[y-1];
}
catch(Exception e){throw new Exception();}
}
else{
return INFINITO;
}
}


//no pincha
public JLista camino_minimo(Object vertice1, Object vertice2)throws Exception{
int x=lista.busqueda(vertice1);
int y=lista.busqueda(vertice2);
JLista list=new JLista();
if ((x!=-1)&&(y!=-1)){
try{
Disktra(vertice1);

Object pred=vertice2;



while(pred!=vertice1){
list.Incertar(pred,1);
int pre=lista.busqueda(pred);
pred=p[pre-1];

}
}
catch(Exception e){throw new Exception();}
list.Incertar(vertice1,1);
}
return list;
}

public JLista adyacentes(Object vertice)throws Exception{
try{
int x=lista.busqueda(vertice);
JLista lis=new JLista();
if (x!=-1){
int longitud=lista.longitud();
for (int i=0; i<longitud; i++){
if (matriz.debolver_camino(x-1,i)!=INFINITO){
lis.adicionar(lista.nombre(i+1));
}
}
}
return lis;
}
catch (Exception e) {throw new Exception();}
}


}