Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
grafo dfs parcial simulacro
class Parcial {
public ListaGenerica<Vertice<T>> maxBottleneckPath(Grafo<T> g) {
ListaGenerica<ListaGenerica<Vertice<T>>> caminos = new ListaGenerica<ListaGenerica<Vertice<T>>>();
boolean[] visitados;
agregarCaminos(g, indice_s, indice_t, visitados, caminos);
return selectMaxBottleneckPath(caminos)
}
public selectMaxBottleneckPath(paths) { //comparar los pesos de las aristas con menor peso de cada camino
// y quedarse con la de peso maximo
paths.comenzar();
int maxBottleneck = -MAXINT;
while (!paths.fin()) {
ListaGenerica<Vertice<T>> currentPath = paths.proximo();
maxBottleneck = Math.max(maxBottleneck, getBottleneck(currentPath);
}
return maxBottleneck;
}
public int getBottleneck(graph, path) { //Devuelve el peso de la arista de menor peso de las formadas por los vertices.
int bottleneck = MAXINT;
for (int i = 0; i < path.tamanio(); i++) {
bottleneck = Math.min(g.peso(path.elemento(i), path.elemento(i + 1)), bottleneck);
}
}
public void agregarCaminos(Grafo<T> g, int indice_s, int indice_t, boolean[] visitados, ListaGenerica<Vertice<T>> camino) {
visitados[s] =t true;
if (indice_t != indice_s)
ListaGenerica<Arista<T>> ady = s.listaDeAdyacentes();
ady.comenzar();
while (!ady.fin()) {
Arista<T> aristaActual = ady.proximo();
if (!visitados[aristaActual.verticeDestino().posicion()]) {
camino.agregarFinal(aristaActual.verticeDestino());
agregarCaminos(g, aristaActual.verticeDestino().posicion(), t, visitados, camino);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.