Implementación de un grafo

En este blog, te enseñaré cómo implementar un grafo en Java, Python, PHP, C++ y JavaScript en español.

En esta guía, aprenderás a:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript


¿Qué son los grafos?

Son una estructura de dato que modela relaciones entre pares de objetos. Se compone de dos elementos:

✅   Nodo:  Representan los elementos individuales. Se representan como puntos.
✅   Aristas:  Conectan los vértices, indicando la existencia de una relación entre ellos. Las aristas pueden ser dirigidas o no. 




Recorridos de grafos
✅ BFS (Recorrido en anchura):  Dado un nodo, recorremos todos los vecinos primero. Para realizar el algoritmo, se necesita implementar pilas, en caso de no ser recursivo. El código termina cuando no queden nodos por visitar.

✅ DFS (Recorrido profundidad):  Vamos primero al final de un vecino, y nos devolvemos para conocer otras las posibilidades.





Pasos para realizar el algoritmo:
1.- Se declaran tres variables:
✅ Puntero 1 y puntero 2: Se inicializan desde el primer y último elemento del array. 

✅ Área Máxima: Se utilizará para  almacenar el área máxima encontrada hasta el momento.

2.- Se ejecuta un bucle mientras puntero 1 no sea igual a puntero 2.

3.- Se calcula la anchura actual como la diferencia entre puntero 2 y puntero 1.

4.- Se calcula el área actual como el producto de la anchura y el mínimo de las alturas en las posiciones puntero 1 y puntero 2.

5.- Si el área actual es mayor que el valor de área máxima, se actualiza este valor.

6.- Si la altura en puntero 1 es menor o igual que la altura en puntero 2, se incrementa puntero 1, en caso contrario, se decrementa puntero 2.

7.- Se retorna el valor del área máxima.

Presentación

Código en Java

public class Solution {
 
    public int maxArea(int[] altura) {
 
        //paso#1
        int puntero1 = 0;
        int puntero2 = altura.length - 1;
        int areaMaxima = 0;
 
        //paso#2
        while (puntero1 != puntero2) {
 
            //paso#3
            int anchura = puntero2 - puntero1;
 
            //paso#4
            int areaActual;
            areaActual = anchura * Math.min(altura[puntero1], altura[puntero2]);
 
           //paso#5
            if (areaActual > areaMaxima) areaMaxima = areaActual;
 
            //paso#6
            if (altura[puntero1] <= altura[puntero2]) puntero1++;
            else puntero2--; 
        }
        
        //paso#7
        return areaMaxima;
    }
}

Código en php

class Solution {
 
    public function maxArea(array $altura): int {
 
        // Paso #1
        $puntero1 = 0;
        $puntero2 = count($altura) - 1;
        $areaMaxima = 0;
 
        // Paso #2
        while ($puntero1 != $puntero2) {
 
            // Paso #3
            $anchura = $puntero2 - $puntero1;
 
            // Paso #4
            $areaActual = $anchura * min($altura[$puntero1], $altura[$puntero2]);
 
            // Paso #5
            if ($areaActual > $areaMaxima) {
                $areaMaxima = $areaActual;
            }
 
            // Paso #6
            if ($altura[$puntero1] <= $altura[$puntero2]) {
                $puntero1++;
            } else {
                $puntero2--;
            }
        }
 
        // Paso #7
        return $areaMaxima;
    }
}

Código en Python

class Solution(object):
    def maxArea(self, altura):
        # Paso #1
        puntero1 = 0
        puntero2 = len(altura) - 1
        area_maxima = 0
 
        # Paso #2
        while puntero1 != puntero2:
            # Paso #3
            anchura = puntero2 - puntero1
 
            # Paso #4
            area_actual = anchura * min(altura[puntero1], altura[puntero2])
 
            # Paso #5
            if area_actual > area_maxima:
                area_maxima = area_actual
 
            # Paso #6
            if altura[puntero1] <= altura[puntero2]:
                puntero1 += 1
            else:
                puntero2 -= 1
 
        # Paso #7
        return area_maxima

Código en C++

class Solution {
public:
  int maxArea(vector<int> altura) {
    // Paso #1
    int puntero1 = 0;
    int puntero2 = altura.size() - 1;
    int areaMaxima = 0;
 
    // Paso #2
    while (puntero1 != puntero2) {
      // Paso #3
      int anchura = puntero2 - puntero1;
 
      // Paso #4
      int areaActual;
      areaActual = anchura * min(altura[puntero1], altura[puntero2]);
 
      // Paso #5
      if (areaActual > areaMaxima) areaMaxima = areaActual;
 
      // Paso #6
      if (altura[puntero1] <= altura[puntero2]) {
        puntero1++;
      } else {
        puntero2--;
      }
    }
 
    // Paso #7
    return areaMaxima;
  }
};

Código en JavaScript

var maxArea = function(altura) {
    // Paso #1
  let puntero1 = 0;
  let puntero2 = altura.length - 1;
  let areaMaxima = 0;
 
  // Paso #2
  while (puntero1 !== puntero2) {
    // Paso #3
    let anchura = puntero2 - puntero1;
 
    // Paso #4
    let areaActual;
    areaActual = anchura * Math.min(altura[puntero1], altura[puntero2]);
 
    // Paso #5
    if (areaActual > areaMaxima) areaMaxima = areaActual;
 
    // Paso #6
    if (altura[puntero1] <= altura[puntero2]) {
      puntero1++;
    } else {
      puntero2--;
    }
  }
 
  // Paso #7
  return areaMaxima;
};

        
    
Conclusión
En este blog, hemos visto cómo realizar el ejercicio Contenedor con mas agua en Java, Python, PHP, C++ y JavaScript.

Hemos visto ejemplos de código en cada lenguaje de programación.