Introducción a la clase
En esta clase exploraremos dos estructuras de datos avanzadas: Árboles y Grafos. Estas estructuras permiten representar datos de manera jerárquica o en forma de red, siendo fundamentales en aplicaciones como navegadores de archivos, inteligencia artificial, redes sociales y algoritmos de búsqueda en mapas.
¿Qué obtendrás de esta clase?
- Comprender la estructura y funcionamiento de los árboles y grafos.
- Aprender a implementar árboles binarios y grafos en C#.
- Identificar las aplicaciones prácticas de estas estructuras.
- Analizar los algoritmos de recorrido y búsqueda en árboles y grafos.
Árboles en C#
Un árbol es una estructura de datos jerárquica donde cada nodo tiene un nodo padre y puede tener múltiples nodos hijos.
Características de un Árbol
- Un nodo raíz como punto de inicio.
- Cada nodo puede tener múltiples hijos, excepto las hojas.
- Se usa en estructuras como sistemas de archivos, bases de datos y compiladores.
Árbol Binario
Un árbol binario es un tipo especial de árbol donde cada nodo tiene como máximo dos hijos (izquierdo y derecho).
Implementación de un Árbol Binario en C#
using System;
class Nodo
{
public int Valor;
public Nodo Izquierdo, Derecho;
public Nodo(int valor)
{
Valor = valor;
Izquierdo = Derecho = null;
}
}
class ArbolBinario
{
public Nodo Raiz;
public void Insertar(int valor)
{
Raiz = InsertarRecursivo(Raiz, valor);
}
private Nodo InsertarRecursivo(Nodo raiz, int valor)
{
if (raiz == null) return new Nodo(valor);
if (valor < raiz.Valor)
raiz.Izquierdo = InsertarRecursivo(raiz.Izquierdo, valor);
else
raiz.Derecho = InsertarRecursivo(raiz.Derecho, valor);
return raiz;
}
public void RecorrerEnOrden(Nodo raiz)
{
if (raiz != null)
{
RecorrerEnOrden(raiz.Izquierdo);
Console.Write(raiz.Valor + " ");
RecorrerEnOrden(raiz.Derecho);
}
}
}
class Program
{
static void Main()
{
ArbolBinario arbol = new ArbolBinario();
arbol.Insertar(50);
arbol.Insertar(30);
arbol.Insertar(70);
arbol.Insertar(20);
arbol.Insertar(40);
arbol.Insertar(60);
arbol.Insertar(80);
Console.WriteLine("Recorrido en orden:");
arbol.RecorrerEnOrden(arbol.Raiz);
}
}
Grafos en C#
Un grafo es una estructura de datos formada por nodos (vértices) y conexiones (aristas).
Características de un Grafo
- Puede ser dirigido (conexiones con dirección) o no dirigido.
- Puede ser ponderado (las conexiones tienen un costo o peso).
- Se usa en redes sociales, mapas y sistemas de recomendación.
Representación de un Grafo en C# usando Listas de Adyacencia
using System;
using System.Collections.Generic;
class Grafo
{
private Dictionary<int, List<int>> adyacencias = new Dictionary<int, List<int>>();
public void AgregarNodo(int nodo)
{
if (!adyacencias.ContainsKey(nodo))
adyacencias[nodo] = new List<int>();
}
public void AgregarArista(int origen, int destino)
{
if (adyacencias.ContainsKey(origen) && adyacencias.ContainsKey(destino))
{
adyacencias[origen].Add(destino);
adyacencias[destino].Add(origen); // Para grafo no dirigido
}
}
public void MostrarGrafo()
{
foreach (var nodo in adyacencias)
{
Console.Write(nodo.Key + " -> ");
foreach (var vecino in nodo.Value)
Console.Write(vecino + " ");
Console.WriteLine();
}
}
}
class Program
{
static void Main()
{
Grafo grafo = new Grafo();
grafo.AgregarNodo(1);
grafo.AgregarNodo(2);
grafo.AgregarNodo(3);
grafo.AgregarNodo(4);
grafo.AgregarArista(1, 2);
grafo.AgregarArista(1, 3);
grafo.AgregarArista(2, 4);
Console.WriteLine("Representación del Grafo:");
grafo.MostrarGrafo();
}
}
Comparación entre Árboles y Grafos
| Característica | Árboles | Grafos |
|---|---|---|
| Estructura | Jerárquica | Red interconectada |
| Ciclos | No puede haber ciclos | Puede haber ciclos |
| Uso común | Sistemas de archivos, bases de datos | Redes sociales, mapas GPS |
| Recorridos | Preorden, inorden, postorden | BFS, DFS |
Caso de uso real
Un navegador de rutas GPS usa un grafo ponderado para encontrar la ruta más corta entre dos ubicaciones.
Ejemplo en C#: Algoritmo de Búsqueda en Grafos (BFS – Breadth First Search)
using System;
using System.Collections.Generic;
class Grafo
{
private Dictionary<int, List<int>> adyacencias = new Dictionary<int, List<int>>();
public void AgregarNodo(int nodo)
{
if (!adyacencias.ContainsKey(nodo))
adyacencias[nodo] = new List<int>();
}
public void AgregarArista(int origen, int destino)
{
adyacencias[origen].Add(destino);
adyacencias[destino].Add(origen);
}
public void BFS(int inicio)
{
Queue<int> cola = new Queue<int>();
HashSet<int> visitados = new HashSet<int>();
cola.Enqueue(inicio);
visitados.Add(inicio);
while (cola.Count > 0)
{
int nodo = cola.Dequeue();
Console.Write(nodo + " ");
foreach (var vecino in adyacencias[nodo])
{
if (!visitados.Contains(vecino))
{
cola.Enqueue(vecino);
visitados.Add(vecino);
}
}
}
}
}
class Program
{
static void Main()
{
Grafo grafo = new Grafo();
grafo.AgregarNodo(1);
grafo.AgregarNodo(2);
grafo.AgregarNodo(3);
grafo.AgregarNodo(4);
grafo.AgregarArista(1, 2);
grafo.AgregarArista(1, 3);
grafo.AgregarArista(2, 4);
Console.WriteLine("BFS desde nodo 1:");
grafo.BFS(1);
}
}
Este código muestra cómo recorrer un grafo usando BFS, un algoritmo clave en la búsqueda de caminos en mapas.
Desafío práctico
Ejercicio:
- Implementa un árbol binario de búsqueda y permite la búsqueda de un número dentro de él.
- Crea un grafo dirigido y permite al usuario ingresar conexiones entre nodos. Luego, implementa BFS para recorrerlo.
Resumen de la clase
- Árboles: Representan estructuras jerárquicas como sistemas de archivos.
- Grafos: Modelan redes como mapas y redes sociales.
- Algoritmos de recorrido en grafos como BFS para búsquedas eficientes.
- Caso de uso real aplicado a GPS y redes.
Próxima clase: Algoritmos de Búsqueda – Binaria, BFS y DFS
En la siguiente clase exploraremos los principales algoritmos de búsqueda utilizados para localizar datos de manera eficiente, comparando sus ventajas y aplicabilidad en diferentes escenarios.
