Árboles y grafos básicos C

Vista previa del material en texto

Árboles y grafos básicos C++
Los árboles y los grafos son estructuras de datos fundamentales en la teoría de grafos y la
programación. Ambos se utilizan para representar relaciones entre elementos, pero
difieren en su estructura y características.
Comencemos por los árboles. Un árbol es una estructura de datos jerárquica en la que los
elementos se organizan en niveles, comenzando desde un nodo raíz y extendiéndose hacia
abajo en ramas o subárboles. Cada nodo puede tener cero o más nodos hijos, excepto el
nodo raíz que no tiene un nodo padre. Los árboles se utilizan para representar estructuras
como árboles genealógicos, estructuras de directorios en un sistema operativo, entre
otros.
En un árbol, cada nodo puede tener un número arbitrario de hijos, pero solo puede tener
un nodo padre. Además, no puede haber ciclos en un árbol, lo que significa que no puede
haber una ruta que regrese a un nodo anterior. Los árboles se pueden recorrer de
diferentes maneras, como el recorrido en profundidad (preorden, inorden, postorden) y el
recorrido en anchura (nivel por nivel).
En la programación, los árboles se pueden implementar utilizando estructuras de datos
como nodos y punteros. Cada nodo contiene un valor y punteros a sus nodos hijos. Aquí
tienes un ejemplo de cómo se puede implementar un árbol binario en C++:
#include <iostream>
struct Nodo {
 int valor;
 Nodo* izquierdo;
 Nodo* derecho;
 Nodo(int val) : valor(val), izquierdo(nullptr), derecho(nullptr) {}
};
int main() {
 Nodo* raiz = new Nodo(1);
 raiz->izquierdo = new Nodo(2);
 raiz->derecho = new Nodo(3);
 raiz->izquierdo->izquierdo = new Nodo(4);
 raiz->izquierdo->derecho = new Nodo(5);
 // Realizar operaciones en el árbol...
 return 0;
}
En este ejemplo, creamos un árbol binario con cinco nodos. Cada nodo contiene un valor
y punteros a sus nodos hijos. La raíz tiene un valor de 1, su hijo izquierdo tiene un valor
de 2 y su hijo derecho tiene un valor de 3. El hijo izquierdo a su vez tiene un hijo
izquierdo con un valor de 4 y un hijo derecho con un valor de 5.
Pasemos ahora a los grafos. Un grafo es una estructura de datos que consta de un
conjunto de nodos (vértices) y un conjunto de aristas que conectan estos nodos. Los
grafos se utilizan para representar relaciones complejas entre elementos, como redes
sociales, mapas de carreteras, entre otros.
En un grafo, las aristas pueden ser dirigidas o no dirigidas. En un grafo dirigido, las
aristas tienen una dirección específica, mientras que en un grafo no dirigido, las aristas no
tienen una dirección específica y se pueden recorrer en ambas direcciones. Además, los
grafos pueden ser ponderados o no ponderados, lo que significa que las aristas pueden
tener un peso asociado o no.
En la programación, los grafos se pueden implementar utilizando estructuras de datos
como listas de adyacencia o matrices de adyacencia. En una lista de adyacencia, cada
nodo tiene una lista de los nodos a los que está conectado, mientras que en una matriz de
adyacencia, se utiliza una matriz para representar las conexiones entre los nodos.
Aquí tienes un ejemplo de cómo se puede implementar un grafo no dirigido utilizando
una lista de adyacencia en C++:
#include <iostream>
#include <vector>
void agregarArista(std::vector<int> grafo[], int origen, int destino) {
 grafo[origen].push_back(destino);
 grafo[destino].push_back(origen);
}
void imprimirGrafo(std::vector<int> grafo[], int numNodos) {
 for (int i = 0; i < numNodos; i++) {
 std::cout << "Nodo " << i << ": ";
 for (int j : grafo[i]) {
 std::cout << j << " ";
 }
 std::cout << std::endl;
 }
}
int main() {
 int numNodos = 5;
 std::vector<int> grafo[numNodos];
 agregarArista(grafo, 0, 1);
 agregarArista(grafo, 0, 4);
 agregarArista(grafo, 1, 2);
 agregarArista(grafo, 1, 3);
 agregarArista(grafo, 1, 4);
 agregarArista(grafo, 2, 3);
 agregarArista(grafo, 3, 4);
 imprimirGrafo(grafo, numNodos);
 return 0;
}
En este ejemplo, creamos un grafo no dirigido con cinco nodos utilizando una lista de
adyacencia. Luego, agregamos aristas entre los nodos utilizando la función
agregarArista(). Finalmente, imprimimos el grafo utilizando la función imprimirGrafo().
En resumen, los árboles y los grafos son estructuras de datos fundamentales en la
programación. Los árboles se utilizan para representar estructuras jerárquicas, mientras
que los grafos se utilizan para representar relaciones complejas. Ambos se pueden
implementar en C++ utilizando diferentes estructuras de datos y algoritmos.