Introducción a la clase
En esta clase aprenderemos sobre los algoritmos de búsqueda, fundamentales para localizar datos dentro de estructuras de datos como arrays, árboles y grafos. Exploraremos tres tipos de búsqueda: búsqueda lineal, búsqueda binaria y los algoritmos de búsqueda en grafos (BFS y DFS).
¿Qué obtendrás de esta clase?
- Comprender la diferencia entre los distintos tipos de búsqueda.
- Implementar búsqueda lineal y binaria en arrays en C#.
- Aprender BFS (Breadth First Search) y DFS (Depth First Search) en grafos.
- Aplicar estos algoritmos en casos reales.
Búsqueda Lineal
La búsqueda lineal recorre todos los elementos de una estructura hasta encontrar el valor deseado.
Características de la Búsqueda Lineal
- No requiere que los datos estén ordenados.
- Tiene una complejidad de O(n) en el peor de los casos.
- Funciona en cualquier estructura de datos lineal (listas, arrays).
Implementación en C#
using System;
class Program
{
static int BusquedaLineal(int[] arreglo, int objetivo)
{
for (int i = 0; i < arreglo.Length; i++)
{
if (arreglo[i] == objetivo)
return i; // Devuelve la posición donde se encontró
}
return -1; // No encontrado
}
static void Main()
{
int[] numeros = { 3, 7, 12, 19, 25 };
Console.WriteLine("Ingrese un número a buscar:");
int objetivo = Convert.ToInt32(Console.ReadLine());
int indice = BusquedaLineal(numeros, objetivo);
Console.WriteLine(indice != -1 ? $"Número encontrado en la posición {indice}" : "Número no encontrado.");
}
}
Búsqueda Binaria
La búsqueda binaria divide el array en mitades y descarta la mitad que no contiene el elemento buscado.
Características de la Búsqueda Binaria
- Requiere que los datos estén ordenados.
- Tiene una complejidad de O(log n), mucho más eficiente que la búsqueda lineal.
- Se usa en estructuras ordenadas como arrays y árboles binarios de búsqueda.
Implementación en C#
using System;
class Program
{
static int BusquedaBinaria(int[] arreglo, int objetivo)
{
int izquierda = 0, derecha = arreglo.Length - 1;
while (izquierda <= derecha)
{
int medio = izquierda + (derecha - izquierda) / 2;
if (arreglo[medio] == objetivo)
return medio;
else if (arreglo[medio] < objetivo)
izquierda = medio + 1;
else
derecha = medio - 1;
}
return -1;
}
static void Main()
{
int[] numeros = { 3, 7, 12, 19, 25 };
Console.WriteLine("Ingrese un número a buscar:");
int objetivo = Convert.ToInt32(Console.ReadLine());
int indice = BusquedaBinaria(numeros, objetivo);
Console.WriteLine(indice != -1 ? $"Número encontrado en la posición {indice}" : "Número no encontrado.");
}
}
Comparación entre Búsqueda Lineal y Binaria
| Algoritmo | Mejor caso | Peor caso | Requiere orden |
|---|---|---|---|
| Búsqueda Lineal | O(1) | O(n) | No |
| Búsqueda Binaria | O(1) | O(log n) | Sí |
Búsqueda en Grafos – BFS y DFS
En estructuras como grafos y árboles, se utilizan algoritmos especializados para recorrer y buscar nodos.
BFS (Breadth-First Search) – Búsqueda en Anchura
BFS explora los nodos nivel por nivel, utilizando una cola (Queue). Es útil para encontrar el camino más corto en un grafo no ponderado.
Implementación de BFS en C#
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); // Grafo no dirigido
}
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);
}
}
DFS (Depth-First Search) – Búsqueda en Profundidad
DFS explora lo más profundo posible en un camino antes de retroceder, utilizando una pila (Stack). Es útil para explorar todas las conexiones posibles en un grafo.
Implementación de DFS en C#
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 DFS(int inicio, HashSet<int> visitados)
{
if (!visitados.Contains(inicio))
{
Console.Write(inicio + " ");
visitados.Add(inicio);
foreach (var vecino in adyacencias[inicio])
{
DFS(vecino, visitados);
}
}
}
}
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("DFS desde nodo 1:");
grafo.DFS(1, new HashSet<int>());
}
}
Caso de uso real
Los algoritmos de búsqueda en grafos se utilizan en GPS y mapas para encontrar la ruta más corta entre dos ubicaciones, optimizando el tiempo de viaje.
Desafío práctico
Ejercicio:
- Implementa un programa que permita buscar un número en un array usando búsqueda lineal y binaria.
- Crea un grafo dirigido y permite buscar un nodo usando BFS y DFS.
Resumen de la clase
- Búsqueda lineal: Recorre todos los elementos hasta encontrar el objetivo (O(n)).
- Búsqueda binaria: Divide el array en mitades para encontrar el objetivo (O(log n)).
- BFS y DFS: Algoritmos para recorrer grafos y árboles eficientemente.
- Caso de uso real aplicado a GPS y redes.
Próxima clase: Algoritmos de Ordenación – Bubble Sort, Merge Sort, Quick Sort
En la siguiente clase aprenderemos sobre los principales algoritmos de ordenación, comparando su eficiencia y cuándo usarlos en aplicaciones reales.
