Cómo funcionan los algoritmos
Chapter 5 Graphs

Capítulo 5: Grafos en Algoritmos

Los grafos son una estructura de datos fundamental que modelan conexiones y relaciones entre objetos. Tienen aplicaciones de amplio alcance en la informática y más allá, desde el modelado de redes sociales y enlaces de páginas web, hasta la resolución de problemas en transporte, programación y asignación de recursos. En este capítulo, exploramos las propiedades básicas y los algoritmos para trabajar con grafos, centrándonos en grafos no dirigidos, búsqueda en profundidad y amplitud, árboles de expansión mínima y caminos más cortos.

Grafos no dirigidos

Un grafo no dirigido es un conjunto de vértices (o nodos) conectados por aristas. Formalmente, definimos un grafo no dirigido G como un par (V, E), donde V es un conjunto de vértices y E es un conjunto de pares no ordenados de vértices, llamados aristas. Una arista (v, w) conecta los vértices v y w. Decimos que v y w son adyacentes o vecinos. El grado de un vértice es el número de aristas incidentes a él.

Aquí hay un ejemplo simple de un grafo no dirigido:

   A --- B
  /     / \
 /     /   \
C --- D --- E

En este grafo, el conjunto de vértices V = {A, B, C, D, E} y el conjunto de aristas E = {(A, B), (A, C), (B, D), (B, E), (C, D), (D, E)}.

Hay varias formas de representar un grafo en un programa. Dos representaciones comunes son:

  1. Matriz de adyacencia: Una matriz booleana n x n A, donde n es el número de vértices. La entrada A[i][j] es verdadera si hay una arista del vértice i al vértice j, y falsa de lo contrario.

  2. Listas de adyacencia: Una matriz Adj de tamaño n, donde n es el número de vértices. La entrada Adj[v] es una lista que contiene los vecinos de v.

La elección de la representación depende de la densidad del grafo (relación entre el número de aristas y el número de vértices) y de las operaciones que necesitamos realizar. Las matrices de adyacencia son simples, pero pueden ser ineficientes para grafos dispersos. Las listas de adyacencia son más eficientes en espacio para grafos dispersos y proporcionan un acceso más rápido a los vecinos de un vértice.

Aquí hay un ejemplo de cómo podríamos representar el grafo anterior usando listas de adyacencia en Java:

List<Integer>[] graph = (List<Integer>[]) new List[5];
graph[0] = Arrays.asList(1, 2);        // A -> B, C
graph[1] = Arrays.asList(0, 3, 4);     // B -> A, D, E
graph[2] = Arrays.asList(0, 3);        // C -> A, D
graph[3] = Arrays.asList(1, 2, 4);     // D -> B, C, E
graph[4] = Arrays.asList(1, 3);        // E -> B, D

Búsqueda en Profundidad (DFS)

La búsqueda en profundidad (DFS) es un algoritmo fundamental de recorrido de grafos que explora lo más lejos posible a lo largo de cada rama antes de retroceder. Puede utilizarse para resolver muchos problemas de grafos, como encontrar componentes conectados, ordenación topológica y detección de ciclos.

El algoritmo DFS funciona de la siguiente manera:

  1. Comenzar en un vértice de origen s.
  2. Marcar el vértice actual como visitado.
  3. Visitar recursivamente todos los vértices no marcados w adyacentes al vértice actual.
  4. Si todos los vértices adyacentes al vértice actual han sido visitados, retroceder al vértice desde el cual se exploró el vértice actual.
  5. Si quedan vértices sin marcar, seleccionar uno y repetir desde el paso 1.

Aquí hay una implementación sencilla de DFS en Java utilizando listas de adyacencia:

boolean[] visited;
 
void dfs(List<Integer>[] graph, int v) {
    // Marcar el vértice actual como visitado
    visited[v] = true;
    // Visitar recursivamente todos los vértices no visitados adyacentes al vértice actual
    for (int w : graph[v]) {
        if (!visited[w]) {
            dfs(graph, w);
        }
    }
}

Para realizar un recorrido DFS completo, llamamos a dfs(graph, s) para cada vértice s en el grafo, donde visited se inicializa en false para todos los vértices.

DFS tiene muchas aplicaciones. Por ejemplo, podemos usarlo para encontrar componentes conectados en un grafo no dirigido ejecutando DFS desde cada vértice no visitado y asignando cada vértice a un componente en función del árbol DFS.

Búsqueda en Anchura (BFS)

La búsqueda en anchura (BFS) es otro algoritmo fundamental de recorrido de grafos que explora los vértices por capas. Visita todos los vértices en el nivel de profundidad actual antes de pasar a los vértices en el siguiente nivel de profundidad.

El algoritmo BFS funciona de la siguiente manera:

  1. Comenzar en un vértice de origen s y marcarlo como visitado.
  2. Encolar s en una cola FIFO.
  3. Mientras la cola no esté vacía: a. Desencolar un vértice v de la cola. b. Para cada vértice w adyacente a v que no haya sido visitado: i. Marcar w como visitado. ii. Encolar w en la cola.Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos pero el código sin traducir:

Mientras la cola no esté vacía:

  • Desencolar un vértice v.
  • Para cada vértice no marcado w adyacente a v:
    • Marcar w como visitado.
    • Encolar w.

Aquí hay una implementación en Java de BFS utilizando listas de adyacencia:

boolean[] visited;
 
void bfs(List<Integer>[] graph, int s) {
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.offer(s);
 
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph[v]) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

BFS es particularmente útil para encontrar los caminos más cortos en grafos no ponderados. La distancia desde el vértice fuente a cualquier otro vértice es el número mínimo de aristas en un camino entre ellos. BFS garantiza encontrar el camino más corto.

Árboles de Expansión Mínima

Un árbol de expansión mínima (MST) es un subconjunto de las aristas de un grafo no dirigido, conexo y con pesos en las aristas, que conecta todos los vértices, sin ciclos y con el peso total mínimo posible.

Dos algoritmos clásicos para encontrar MSTs son el algoritmo de Kruskal y el algoritmo de Prim.

El algoritmo de Kruskal funciona de la siguiente manera:

  1. Crear un bosque F donde cada vértice es un árbol separado.
  2. Crear un conjunto S que contenga todas las aristas del grafo.
  3. Mientras S no esté vacío y F aún no sea un árbol de expansión:
    • Eliminar una arista de peso mínimo de S.
    • Si la arista eliminada conecta dos árboles diferentes, añadirla a F, combinando dos árboles en uno solo.

El algoritmo de Prim funciona de la siguiente manera:

  1. Inicializar un árbol con un solo vértice, elegido arbitrariamente del grafo.
  2. Expandir el árbol por una arista: de todas las aristas que conectan el árbol con vértices que aún no están en el árbol, encontrar la arista de peso mínimo y transferirla al árbol.
  3. Repetir el paso 2 hasta que todos los vértices estén en el árbol.

Aquí hay una implementación en Java del algoritmo de Prim:

int minKey(int[] key, boolean[] mstSet, int V) {
    int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++) {
        // Si el vértice v no está en el conjunto mstSet y su clave es menor que el mínimo actual
        if (!mstSet[v] && key[v] < min) {
            // Actualizar el mínimo y el índice del mínimo
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
 
void primMST(int[][] graph, int V) {
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];
 
    // Inicializar todas las claves a infinito y todos los vértices como no incluidos en el MST
    for (int i = 0; i < V; i++) {
        key[i] = Integer.MAX_VALUE;
        mstSet[i] = false;
    }
 
    // Establecer la clave del vértice 0 a 0 y su padre a -1
    key[0] = 0;
    parent[0] = -1;
 
    // Construir el MST
    for (int count = 0; count < V - 1; count++) {
        // Seleccionar el vértice con la clave mínima que no está en el MST
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
 
        // Actualizar las claves de los vértices adyacentes a u
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
 
    printMST(parent, graph, V);
}

Los árboles de expansión mínima (MST) tienen muchas aplicaciones, como el diseño de redes (comunicación, eléctrica, hidráulica, informática) y la aproximación de problemas del viajante de comercio.

Caminos más cortos

El problema del camino más corto consiste en encontrar un camino entre dos vértices en un grafo de tal manera que la suma de los pesos de sus aristas sea mínima. Este problema tiene muchas variaciones, como caminos más cortos de un solo origen, caminos más cortos entre todos los pares de vértices y caminos más cortos a un solo destino.

El algoritmo de Dijkstra es un algoritmo codicioso que resuelve el problema de los caminos más cortos de un solo origen para un grafo con pesos de aristas no negativos. Funciona de la siguiente manera:

  1. Crear un conjunto sptSet (conjunto del árbol de caminos más cortos) que realiza un seguimiento de los vértices incluidos en el árbol de caminos más cortos.
  2. Asignar un valor de distancia a todos los vértices del grafo. Inicializar todos los valores de distancia como INFINITO. Asignar el valor de distancia como 0 para el vértice de origen.
  3. Mientras sptSet no incluya todos los vértices, seleccionar un vértice v que no esté en sptSet y tenga el valor de distancia mínimo. Incluir v en sptSet.
  4. Actualizar los valores de distancia de todos los vértices adyacentes a v. Para actualizar los valores de distancia, iterar a través de todos los vértices adyacentes. Para cada vértice adyacente w, si la suma de la distancia de v más el peso de la arista (v, w) es menor que la distancia actual de w, actualizar la distancia de w.Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos, pero sin traducir el código:

El valor de v (desde la fuente) y el peso del borde v-w es menor que el valor de distancia de w, entonces actualiza el valor de distancia de w.

Aquí hay una implementación en Java del algoritmo de Dijkstra:

public void dijkstra(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
    boolean[] sptSet = new boolean[V];
 
    // Inicializar las distancias a todos los vértices como infinito y el conjunto de vértices más cortos como falso
    for (int i = 0; i < V; i++) {
        dist[i] = Integer.MAX_VALUE;
        sptSet[i] = false;
    }
 
    // La distancia desde la fuente a sí misma es 0
    dist[src] = 0;
 
    // Encontrar el vértice más cercano no incluido en el conjunto de vértices más cortos
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
        // Actualizar las distancias de los vértices adyacentes a u
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    printSolution(dist);
}

El algoritmo de Bellman-Ford es otro algoritmo para encontrar los caminos más cortos desde un solo vértice fuente a todos los demás vértices en un grafo dirigido con pesos. A diferencia del algoritmo de Dijkstra, el algoritmo de Bellman-Ford puede manejar gráficos con pesos de borde negativos, siempre que no haya ciclos de peso negativo.

El algoritmo funciona de la siguiente manera:

  1. Inicializar las distancias desde la fuente a todos los vértices como infinito y la distancia al vértice fuente como 0.
  2. Relajar todos los bordes |V| - 1 veces. Para cada borde u-v, si la distancia a v se puede acortar tomando el borde u-v, actualizar la distancia a v.
  3. Verificar los ciclos de peso negativo. Ejecutar un paso de relajación para todos los bordes. Si se produce algún cambio de distancia, entonces hay un ciclo de peso negativo.

Aquí hay una implementación en Java del algoritmo de Bellman-Ford:

public void bellmanFord(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
 
    // Inicializar las distancias a todos los vértices como infinito
    for (int i = 0; i < V; i++)
        dist[i] = Integer.MAX_VALUE;
    // La distancia desde la fuente a sí misma es 0
    dist[src] = 0;
 
    // Relajar todos los bordes |V| - 1 veces
    for (int i = 1; i < V; i++) {
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
 
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }
    }
 
    printSolution(dist);
}

Los algoritmos de rutas más cortas tienen numerosas aplicaciones, como en los sistemas de navegación, los protocolos de enrutamiento de red y la planificación del transporte. Son herramientas fundamentales en la teoría de grafos y son esenciales en muchas tareas de procesamiento de grafos.

Conclusión

Los gráficos son estructuras de datos versátiles y poderosas que pueden modelar una amplia variedad de problemas. En este capítulo, exploramos las propiedades y tipos básicos de los gráficos, y estudiamos algoritmos gráficos fundamentales, incluida la búsqueda en profundidad, la búsqueda en anchura, los árboles de expansión mínima y las rutas más cortas.

La búsqueda en profundidad y la búsqueda en anchura proporcionan formas sistemáticas de explorar un gráfico y forman la base de muchos algoritmos gráficos avanzados. Los algoritmos de árbol de expansión mínima como Kruskal y Prim encuentran un árbol que conecta todos los vértices con el peso total mínimo de los bordes. Los algoritmos de ruta más corta como Dijkstra y Bellman-Ford encuentran rutas de peso mínimo entre vértices.

Comprender estos conceptos y algoritmos básicos es crucial para trabajar de manera efectiva con gráficos y abordar problemas complejos en varios dominios. A medida que avance en su estudio de algoritmos, encontrará algoritmos gráficos más avanzados que se basan en estas técnicas fundamentales.

Los gráficos proporcionan un lenguaje poderoso para describir y resolver problemas en informática y más allá. Dominar los algoritmos de gráficos lo equipará con un conjunto de herramientas versátil para modelar y resolver una amplia gama de problemas computacionales.Here is the Spanish translation for the provided Markdown file, with the code comments translated:

Desafíos Nacionales

Introducción

Este repositorio contiene una serie de desafíos nacionales que se pueden utilizar para practicar y mejorar las habilidades de programación.

Desafíos

  1. Calculadora de Impuestos

    • Descripción: Crea una aplicación que calcule el impuesto sobre la renta de una persona en función de su ingreso anual.
    • Lenguaje: Python
    • Archivo: tax_calculator.py
    # Pide al usuario que ingrese su ingreso anual
annual_income = float(input("Ingrese su ingreso anual: "))
 
# Calcula el impuesto sobre la renta
if annual_income <= 10000:
    tax_rate = 0.1
elif annual_income <= 50000:
    tax_rate = 0.2
else:
    tax_rate = 0.3
 
tax_amount = annual_income * tax_rate
 
# Muestra el monto del impuesto
print(f"El impuesto sobre la renta es: {tax_amount:.2f}")

  2. Conversor de Moneda

    • Descripción: Desarrolla una aplicación que convierta una cantidad de dinero de una moneda a otra.
    • Lenguaje: JavaScript
    • Archivo: currency_converter.js
    // Pide al usuario que ingrese el monto y la moneda de origen
const amount = parseFloat(prompt("Ingrese el monto a convertir:"));
const fromCurrency = prompt("Ingrese la moneda de origen (USD, EUR, GBP, etc.):");
 
// Pide al usuario que ingrese la moneda de destino
const toCurrency = prompt("Ingrese la moneda de destino (USD, EUR, GBP, etc.):");
 
// Realiza la conversión de moneda
const conversionRate = getConversionRate(fromCurrency, toCurrency);
const convertedAmount = amount * conversionRate;
 
// Muestra el resultado de la conversión
console.log(`${amount} ${fromCurrency} es igual a ${convertedAmount.toFixed(2)} ${toCurrency}`);
 
// Función para obtener el tipo de cambio entre dos monedas
function getConversionRate(from, to) {
    // Implementa la lógica para obtener el tipo de cambio aquí
    // Puedes utilizar una API de tipo de cambio o una tabla de tipos de cambio predefinidos
    // Devuelve el tipo de cambio correspondiente
}

  3. Generador de Contraseñas

    • Descripción: Crea una aplicación que genere contraseñas seguras y aleatorias.
    • Lenguaje: Python
    • Archivo: password_generator.py
    # Importa los módulos necesarios
import string
import random
 
# Pide al usuario que ingrese la longitud de la contraseña
password_length = int(input("Ingrese la longitud de la contraseña: "))
 
# Genera la contraseña
characters = string.ascii_letters + string.digits + string.punctuation
password = ''.join(random.choice(characters) for i in range(password_length))
 
# Muestra la contraseña generada
print(f"La contraseña generada es: {password}")

  4. Juego de Adivinar el Número

    • Descripción: Desarrolla un juego en el que el usuario tenga que adivinar un número aleatorio.
    • Lenguaje: JavaScript
    • Archivo: guess_the_number.js
    // Genera un número aleatorio entre 1 y 100
const targetNumber = Math.floor(Math.random() * 100) + 1;
 
// Inicializa el número de intentos
let attempts = 0;
 
// Bucle del juego
while (true) {
    // Pide al usuario que ingrese un número
    const guess = parseInt(prompt("Adivina el número (entre 1 y 100):"));
 
    // Incrementa el número de intentos
    attempts++;
 
    // Verifica si el número adivinado es correcto
    if (guess === targetNumber) {
        console.log(`¡Felicidades, adivinaste el número en ${attempts} intentos!`);
        break;
    } else if (guess < targetNumber) {
        console.log("El número es más alto.");
    } else {
        console.log("El número es más bajo.");
    }
}

¡Disfruta de estos desafíos y mejora tus habilidades de programación!

Chapter 4 Searching AlgorithmsChapter 6 Strings