Ejercicios Resueltos de Algoritmos con Grafos en Java

Ejercicios Resueltos de Grafos en Java

A continuación, se presenta una colección de ejercicios prácticos implementados en Java para la manipulación y resolución de problemas sobre la teoría de grafos, utilizando estructuras como Iterator, Vector, Vertice y Arco.

Ejercicio 1: Búsqueda de Predecesores

Métodos para obtener los vértices predecesores de un vértice dado en un grafo, ya sea recorriendo los arcos o explorando los vértices adyacentes.

public static Iterator<Vertice> predecesores (Grafo g, Vertice v ){
    Vector<Vertice> pred = new Vector<>();
    Iterator<Arco> itAr = g.arcos();
    while(itAr.hasNext()){
        Arco a = itAr.next();
        if (a.getDestino().equals(v)) pred.add(a.getOrigen()); 
    }
    return pred.iterator(); 
}

public static Iterator<Vertice> predecesores2 (Grafo g, Vertice v ){
    Vector<Vertice> pred = new Vector<>();
    Iterator<Vertice> itVer = g.vertices();
    while (itVer.hasNext()){
        Vertice w = itVer.next();
        Iterator<Vertice> itAdy = g.adyacentes(w);
        while (itAdy.hasNext()) 
            if (itAdy.next().equals(v)) pred.add(w);
    }
    return pred.iterator(); 
}

Ejercicio 2: Verificación de Sumidero

Algoritmo para determinar si un vértice específico actúa como un sumidero dentro del grafo.

public static boolean sumidero (Grafo g, Vertice v){
    // Número de vértices
    Iterator<Vertice> itVer = g.vertices(); 
    int numVertices = 0;
    while (itVer.hasNext()){
        itVer.next(); 
        numVertices++; 
    }
    // Grado de entrada
    itVer = predecesores(g, v); 
    int numPred = 0;
    while (itVer.hasNext()){
        itVer.next(); 
        numPred++; 
    }
    // Grado de salida
    itVer = g.adyacentes(v); 
    int numAdy = 0;
    while (itVer.hasNext()){
        itVer.next();
        numAdy++;
    }
    return numAdy == 0 && numPred == numVertices - 1;
}

Ejercicio 3: Comprobación de Grafo Regular

Función que comprueba si todos los vértices del grafo poseen el mismo grado de adyacencia.

public static boolean regular (Grafo g){
    if (g.esVacio()) return true;
    Iterator<Vertice> itVer = g.vertices();
    Vertice v = itVer.next();
    Iterator<Vertice> itAdy = g.adyacentes(v);
    int numAdy = 0;
    while (itAdy.hasNext()){
        numAdy++;
        itAdy.next();
    }
    while (itVer.hasNext()){
        v = itVer.next();
        itAdy = g.adyacentes(v);
        int contador = 0;
        while (itAdy.hasNext()){
            contador++;
            itAdy.next();
        }
        if (contador != numAdy)
            return false;
    }
    return true;
}

Ejercicio 4: Existencia de Camino entre Dos Vértices

Métodos basados en búsqueda para comprobar si existe un camino conectando dos vértices determinados.

public static boolean hayCaminoEntreDos (Grafo g, Vertice v1, Vertice v2){
    Vector<Vertice> visitados = new Vector<>();
    return caminoEntreDos(g, v1, v2, visitados);
}

private static boolean caminoEntreDos (Grafo g, Vertice v1, Vertice v2, Vector<Vertice> visitados){
    boolean encontrado = false; 
    visitados.add(v1);
    if (v1.equals(v2)) return true;
    else { 
        Iterator<Vertice> adys = g.adyacentes(v1);
        while (adys.hasNext() && !encontrado){
            Vertice w = adys.next();
            if (!visitados.contains(w))
                encontrado = caminoEntreDos(g, w, v2, visitados); 
        }
        return encontrado; 
    } 
}

Ejercicio 5: Recorridos, Arborescencia y Ciclos

Conjunto de funciones avanzadas que incluyen el cálculo del tamaño de un iterador, recorridos en profundidad (DFS), detección de arborescencia, nodos no alcanzables y detección de ciclos.

private static int size(Iterator<Vertice> i){
    int cont = 0;
    while(i.hasNext()){
        cont++;
        i.next();
    }
    return cont;
}

// Recorrido en profundidad
public static void profundidad (Grafo g, Vertice v) {
    Vector<Vertice> visitados = new Vector<>();
    profundidad(g, v, visitados);
}

private static void profundidad(Grafo g, Vertice v, Vector<Vertice> visitados)
{
    visitados.add(v);
    Iterator<Vertice> adys = g.adyacentes(v);
    while (adys.hasNext()){
        Vertice w = adys.next();
        if (!visitados.contains(w))
            profundidad(g, w, visitados);
    }
}

public static Vertice esArborescencia (Grafo g){
    Iterator<Vertice> ver = g.vertices();
    while(ver.hasNext()){
        Vector<Vertice> visitados = new Vector<>();
        Vertice v = ver.next();
        profundidad(g, v, visitados);
        // Comparar el conjunto de visitados con el conjunto de vértices del grafo
        if (size(visitados.iterator()) == size(g.vertices())) return v;
    }
    return null;
}

public static Iterator<Vertice> noAlcanzables (Grafo g, Vertice v){
    Vector<Vertice> porVisitar = new Vector<>();
    Iterator<Vertice> itVer = g.vertices();
    while (itVer.hasNext()){
        porVisitar.add(itVer.next());
    }
    return noAlcanzables(g, v, porVisitar);
}

private static Iterator<Vertice> noAlcanzables (Grafo g, Vertice v, Vector<Vertice> porVisitar){
    porVisitar.remove(v);
    Iterator<Vertice> itAdy = g.adyacentes(v);
    while(itAdy.hasNext()){
        Vertice ady = itAdy.next();
        if(porVisitar.contains(ady))
            return noAlcanzables(g, ady, porVisitar);
    }
    return porVisitar.iterator();
}

// Determinar si hay un ciclo que tenga como origen el vértice v
public static boolean hayCiclo(Grafo g, Vertice v){
    Vector<Vertice> visitados = new Vector<>();
    return hayCiclo(g, v, v, visitados);
}

private static boolean hayCiclo(Grafo g, Vertice vOrigen, Vertice v, Vector<Vertice> visitados){
    boolean encontrado = false;
    visitados.add(v);
    Iterator<Vertice> adys = g.adyacentes(v);
    while (adys.hasNext() && !encontrado){
        Vertice w = adys.next();
        if (vOrigen.equals(w))
            encontrado = true;
        else if (!visitados.contains(w))
            encontrado = hayCiclo(g, vOrigen, w, visitados);
    }
    return encontrado;
}