Skip to content

README.md

Latest commit

 

History

History
135 lines (97 loc) · 5.85 KB

README.md

File metadata and controls

135 lines (97 loc) · 5.85 KB

🕸️ Graph – Estructuras de grafos en Python

Esta carpeta contiene implementaciones básicas de estructuras de grafos y algunos algoritmos fundamentales de recorrido. Los grafos son estructuras no lineales compuestas por nodos (vértices) y conexiones entre ellos (aristas), ampliamente utilizados en redes, mapas, inteligencia artificial, compiladores, etc.

📂 Archivos incluidos

Archivo Descripción
adjacency_list.py Implementación de un grafo utilizando lista de adyacencia
adjacency_matrix.py Implementación de un grafo utilizando matriz de adyacencia
traversal.py Algoritmos de recorrido: BFS (Breadth-First Search) y DFS (Depth-First Search)

▶️ Cómo usar

Ejecuta cada script directamente para ver ejemplos de uso:

python adjacency_list.py
python adjacency_matrix.py
python traversal.py

🧠 ¿Qué es un grafo?

Un grafo está formado por:

  • Un conjunto de vértices (o nodos)
  • Un conjunto de aristas (o conexiones) que unen pares de vértices

Puede ser:

  • Dirigido (las conexiones tienen dirección) o no dirigido
  • Ponderado (las aristas tienen peso) o no ponderado

🧮 Representaciones comunes de grafos

✅ Lista de adyacencia (adjacency_list.py)

Eficiente en espacio para grafos dispersos.

grafo = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"]
}

Ventajas:

  • Menor uso de memoria
  • Fácil de recorrer

✅ Matriz de adyacencia (adjacency_matrix.py)

Ideal para grafos densos o cuando se requiere verificar rápidamente si existe una conexión entre dos nodos.

    A  B  C
A [ 0, 1, 1 ]
B [ 1, 0, 0 ]
C [ 1, 0, 0 ]

Ventajas:

  • Verificación rápida de conexiones
  • Buena para algoritmos que requieren operaciones matriciales

🔁 Algoritmos de recorrido (traversal.py)

🔹 BFS – Breadth-First Search

  • Usa una cola (queue)
  • Recorre el grafo nivel por nivel

🔹 DFS – Depth-First Search

  • Usa una pila (implícitamente con recursión o explícitamente)
  • Se sumerge en un camino antes de retroceder

Estos algoritmos sirven para:

  • Encontrar caminos
  • Detectar ciclos
  • Clasificar dependencias
  • Resolver rompecabezas y más

🌍 ¿Para qué sirven los grafos?

Los grafos son una herramienta esencial para representar y resolver problemas en los que hay elementos conectados entre sí. Desde redes sociales hasta navegación GPS, modelan relaciones, rutas, dependencias y estructuras en sistemas complejos.

Un grafo permite representar:

  • Personas y sus relaciones
  • Lugares y las rutas entre ellos
  • Computadoras y sus conexiones
  • Tareas y sus dependencias
  • Páginas web y sus enlaces
  • Elementos químicos y sus reacciones

🏙️ Aplicaciones de grafos en la vida cotidiana y profesional

Área Ejemplo de uso Explicación
🔗 Redes sociales Facebook, Twitter, Instagram Cada usuario es un nodo; las amistades, seguidores o menciones son aristas. Los algoritmos de sugerencia de amigos usan caminos y vecinos comunes.
🛰️ Navegación y mapas Google Maps, Waze Las ciudades y calles son nodos; las rutas, aristas con peso (distancia o tráfico). Los algoritmos buscan el camino más corto o rápido.
🌐 Web e internet Google, motores de búsqueda Cada página web es un nodo; los enlaces entre páginas son aristas. El algoritmo PageRank de Google se basa en grafos.
🛒 Recomendaciones Amazon, Netflix, Spotify Los productos, usuarios o canciones se conectan en un grafo para detectar patrones, similitudes o gustos en común.
💻 Redes de computadoras Diseño de redes LAN/WAN Los dispositivos (routers, switches, PCs) son nodos; los cables o conexiones inalámbricas, las aristas. Se usa para optimizar rutas y detectar fallas.
🔄 Dependencias en software NPM, Python, compiladores Los módulos se conectan en un grafo dirigido que muestra qué depende de qué. Es vital para compilación, actualización o carga de paquetes.
🧬 Biología y medicina Genómica, redes neuronales Las neuronas, genes o proteínas están conectadas y su interacción puede modelarse con grafos para estudiar el comportamiento de sistemas complejos.
📊 Bases de datos Bases de datos orientadas a grafos como Neo4j Permiten consultar relaciones complejas de forma más eficiente que bases de datos relacionales tradicionales. Muy útiles en análisis de fraudes o genealogía.
🤖 Inteligencia Artificial Planificación, razonamiento En IA, los grafos se usan para representar estados, transiciones y relaciones semánticas entre conceptos (grafos de conocimiento).

🎯 ¿Por qué es importante aprender grafos?

  • Porque muchos problemas del mundo real son relacionales: tráfico, relaciones humanas, circuitos, procesos, redes…
  • Porque dominar sus algoritmos (BFS, DFS, Dijkstra, A*, Kruskal, etc.) es esencial para entrevistas técnicas y resolución de problemas complejos.
  • Porque entrenar modelos, construir apps inteligentes o diseñar sistemas eficientes depende muchas veces de saber estructurar y recorrer un grafo.

🔎 Ejemplo cotidiano:

Cuando abres Waze y te recomienda evitar una avenida por tráfico, está usando un grafo donde cada calle es un nodo conectado a otras calles, y cada conexión tiene un peso que representa el tiempo estimado. Luego, usa un algoritmo como Dijkstra para hallar la ruta más rápida.

📚 Recomendaciones

  • Empieza con adjacency_list.py para entender la estructura más intuitiva
  • Usa traversal.py para practicar recorridos y entender cómo se explora un grafo
  • Modifica los grafos de prueba para ver cómo cambian los recorridos

🙌 Créditos

Esta carpeta fue desarrollada como parte del proyecto de estructuras de datos en Python.

Autor: @luuiscc_

Entender grafos es entender cómo se conecta el mundo.