Grafos y Árboles Binarios en Python: Ejemplos Prácticos de Dijkstra, Recorridos y Búsquedas

Implementación de Grafos en Python

A continuación se muestra una implementación de un grafo en Python, con funciones para agregar cámaras, conectarlas y calcular rutas de menor coste mediante el algoritmo de Dijkstra.

class Grafo:
    def __init__(self):
        self.adj_list = {}
        self.valores = {}

    def agregar_camara(self, camara, valor):
        self.adj_list[camara] = []
        self.valores[camara] = valor

    def agregar_conexion(self, camara1, camara2, coste_camino):
        self.adj_list[camara1].append((camara2, coste_camino))
        self.adj_list[camara2].append((camara1, coste_camino))

    def mostrar_grafo(self):
        for camara, conexiones in self.adj_list.items():
            print(f"{camara} (Valor: {self.valores[camara]}) -> {conexiones}")

Funciones de análisis del grafo

Cámara con más conexiones

def camara_con_mas_conexiones(grafo):
    max_conexiones = -1
    camara_max = None
    for camara, conexiones in grafo.adj_list.items():
        if len(conexiones) > max_conexiones:
            max_conexiones = len(conexiones)
            camara_max = camara
    return camara_max, max_conexiones

Conexión con mayor coste

def conexion_mayor_coste(grafo):
    max_coste = -1
    conexion_max = None

    for camara, conexiones in grafo.adj_list.items():
        for vecino, coste_camino in conexiones:
            coste_total = grafo.valores[camara] + grafo.valores[vecino] + coste_camino
            if coste_total > max_coste:
                max_coste = coste_total
                conexion_max = (camara, vecino, coste_total)
    return conexion_max

Camino de menor coste (Dijkstra)

import heapq

def dijkstra_minimizar_coste(grafo, inicio, destino):
    distancias = {camara: float('inf') for camara in grafo.adj_list}
    distancias[inicio] = grafo.valores[inicio]
    cola_prioridad = [(grafo.valores[inicio], inicio, [])]
    camino_optimo = []

    while cola_prioridad:
        coste_actual, camara_actual, camino = heapq.heappop(cola_prioridad)

        if camara_actual == destino:
            camino_optimo = camino + [camara_actual]
            return coste_actual, camino_optimo

        for vecino, coste_camino in grafo.adj_list[camara_actual]:
            nuevo_coste = coste_actual + grafo.valores[vecino] + coste_camino
            if nuevo_coste < distancias[vecino]:
                distancias[vecino] = nuevo_coste
                heapq.heappush(cola_prioridad, (nuevo_coste, vecino, camino + [camara_actual]))
    return float('inf'), []  # Si no hay camino

Uso del grafo

from grafo import Grafo
from funciones import (camara_con_mas_conexiones,
    conexion_mayor_coste, dijkstra_minimizar_coste)

print("Grafo:")
grafo.mostrar_grafo()

camara, conexiones = camara_con_mas_conexiones(grafo)
print(f"\nCámara con más conexiones: {camara} (Conexiones: {conexiones})")

camara1, camara2, coste = conexion_mayor_coste(grafo)
print(f"\nConexión con mayor coste: ({camara1}, {camara2}) - Coste total: {coste}")

coste_total, camino = dijkstra_minimizar_coste(grafo, 1, 4)
print(f"\nCamino óptimo de 1 a 4: {camino} con coste total: {coste_total}")

Agregar cámaras y conexiones

Para construir el grafo se utilizan los métodos agregar_camara y agregar_conexion.

Árbol Binario de Búsqueda de Libros

La siguiente sección implementa una clase Libro, un árbol binario ordenado por título y varias operaciones de consulta.

class Libro:
    def __init__(self, titulo, autor, genero, ...):
        self.titulo = titulo
        ...

    def __repr__(self):
        return f"Libro(titulo='{self.titulo}', ...)"

class NodoArbol:
    def __init__(self, libro):
        self.libro = libro
        self.izquierda = None
        self.derecha = None

class ArbolBinario:
    def __init__(self):
        self.raiz = None

    def insertar(self, libro):
        self.raiz = self._insertar_recursivo(self.raiz, libro)

    def _insertar_recursivo(self, nodo, libro):
        if nodo is None:
            return NodoArbol(libro)
        if libro.titulo < nodo.libro.titulo:
            nodo.izquierda = self._insertar_recursivo(nodo.izquierda, libro)
        else:
            nodo.derecha = self._insertar_recursivo(nodo.derecha, libro)
        return nodo

    def postorden(self):
        resultado = []
        self._postorden_recursivo(self.raiz, resultado)
        return resultado

    def _postorden_recursivo(self, nodo, resultado):
        if nodo:
            self._postorden_recursivo(nodo.izquierda, resultado)
            self._postorden_recursivo(nodo.derecha, resultado)
            resultado.append(nodo.libro)

    def libros_por_clasificacion(self, clasificacion):
        resultado = []
        self._buscar_clasificacion(self.raiz, clasificacion, resultado)
        return resultado

    def _buscar_clasificacion(self, nodo, clasificacion, resultado):
        if nodo:
            self._buscar_clasificacion(nodo.izquierda, clasificacion, resultado)
            self._buscar_clasificacion(nodo.derecha, clasificacion, resultado)
            if nodo.libro.clasificacion == clasificacion:
                resultado.append(nodo.libro)

    def contar_libros_paginas(self, paginas_min):
        return self._contar_paginas_recursivo(self.raiz, paginas_min)

    def _contar_paginas_recursivo(self, nodo, paginas_min):
        if not nodo:
            return 0
        conteo = 1 if nodo.libro.paginas > paginas_min else 0
        conteo += self._contar_paginas_recursivo(nodo.izquierda, paginas_min)
        conteo += self._contar_paginas_recursivo(nodo.derecha, paginas_min)
        return conteo

    def indice_por_genero(self):
        indice = {}
        self._generar_indice(self.raiz, indice)
        return indice

    def _generar_indice(self, nodo, indice):
        if nodo:
            if nodo.libro.genero not in indice:
                indice[nodo.libro.genero] = []
            indice[nodo.libro.genero].append(nodo.libro)
            self._generar_indice(nodo.izquierda, indice)
            self._generar_indice(nodo.derecha, indice)

Ejemplo de uso con lista de libros

# Lista de libros de ejemplo
libros = [
    Libro("El principito", "Antoine de Saint-Exupéry", "Infantil", "Todos", 96, 1943),
    ...
]

# Crear el árbol binario
titulo_arbol = ArbolBinario()
for libro in libros:
    titulo_arbol.insertar(libro)

print("\nRecorrido postorden del árbol:")
print(titulo_arbol.postorden())

print("\nLibros con clasificación 'Adulto':")
print(titulo_arbol.libros_por_clasificacion("Adulto"))

print("\nNúmero de libros con más de 500 páginas:")
print(titulo_arbol.contar_libros_paginas(500))

print("\nÍndice por género:")
indice_genero = titulo_arbol.indice_por_genero()
for genero, libros in indice_genero.items():
    print(f"{genero}: {libros}")