1. Tabla Maestra de Complejidades

2. Punteros en C++

Un puntero es una variable que almacena una direccion de memoria. Es el mecanismo fundamental para construir estructuras dinamicas (listas, arboles, grafos). Si no entiendes punteros, no puedes entender nada de lo que sigue.

2.1 Declaracion y operadores basicos

int x = 42;          // x vive en la direccion 0x100, su valor es 42
int* ptr = &x;       // ptr vive en 0x200, su valor es 0x100 (la direccion de x)
cout << x;            // imprime 42 — el valor de x directamente
cout << ptr;          // imprime 0x100 — la direccion almacenada en ptr
cout << *ptr;         // imprime 42 — dereferencia: el valor EN la direccion que ptr guarda
cout << &x;           // imprime 0x100 — la direccion de x
cout << &ptr;         // imprime 0x200 — la direccion del propio puntero
*ptr = 99;            // cambia el valor en la direccion 0x100, o sea cambia x a 99
cout << x;            // imprime 99 — x fue modificado a traves del puntero

Los dos significados de *:

• En declaracion: int* ptr — “ptr es un puntero a int”
• En uso: *ptr — “dame el valor en la direccion que ptr contiene” (dereferencia)

Los dos significados de &:

• En expresion: &x — “dame la direccion de x” (operador address-of)
• En declaracion de parametro: int& ref — “ref es una referencia a int”

nullptr (o NULL en C) es un puntero que no apunta a nada. Siempre inicializa punteros a nullptr si no tienes un valor aun.

2.2 Stack vs Heap

void ejemplo() {
    int a = 10;               // stack: se destruye al salir de ejemplo()
    int* p = new int(20);     // heap: 20 persiste hasta que hagas delete
    delete p;                 // liberar memoria del heap — obligatorio
}                             // a se destruye aqui automaticamente

Regla: usa stack por defecto. Usa heap cuando necesitas que el dato sobreviva al scope actual, o cuando el tamano es muy grande o desconocido en compilacion.

2.3 Memoria dinamica: new y delete

// Asignar un solo entero en el heap
int* p = new int(42);         // p apunta a un int con valor 42 en el heap
cout << *p;                   // imprime 42
delete p;                     // libera la memoria — obligatorio
p = nullptr;                  // buena practica: evitar dangling pointer

// Asignar un arreglo en el heap
int* arr = new int[5];        // arreglo de 5 enteros en el heap
arr[0] = 10;                  // acceso por indice, igual que arreglo normal
arr[1] = 20;                  // segundo elemento
*(arr + 2) = 30;              // equivalente a arr[2] = 30 (aritmetica de punteros)
delete[] arr;                 // delete con [] para arreglos — NO usar delete sin []
arr = nullptr;                // limpiar el puntero

Reglas de oro:

• Todo new necesita exactamente un delete
• Todo new[] necesita exactamente un delete[]
• Nunca uses delete para lo que asignaste con new[] (comportamiento indefinido)
• Nunca hagas delete dos veces al mismo puntero (double free = crash)
• Nunca uses un puntero despues de hacerle delete (dangling pointer)

2.4 Aritmetica de punteros

int arr[4] = {10, 20, 30, 40};   // arreglo de 4 enteros
int* ptr = arr;                    // nombre del arreglo = puntero al primer elemento
cout << *ptr;                      // imprime 10 — primer elemento
cout << *(ptr + 1);                // imprime 20 — avanza sizeof(int) = 4 bytes
cout << *(ptr + 2);                // imprime 30 — avanza 8 bytes desde el inicio
cout << ptr[3];                    // imprime 40 — ptr[i] es equivalente a *(ptr + i)
ptr++;                             // ptr ahora apunta al segundo elemento (20)
cout << *ptr;                      // imprime 20

Clave: ptr + 1 no avanza 1 byte, avanza sizeof(tipo) bytes. Para int*, avanza 4 bytes. El compilador hace la conversion automaticamente.

Equivalencia arreglo-puntero: arr[i] es exactamente lo mismo que *(arr + i). El nombre de un arreglo decae (decay) a puntero al primer elemento cuando se pasa a una funcion.

2.5 Punteros en estructuras de datos

// Nodo de lista enlazada simple
struct Node {
    int data;                      // el dato almacenado
    Node* next;                    // puntero al siguiente nodo (autoreferencia)
};

// Crear nodos y enlazarlos
Node* a = new Node();              // crear nodo a en el heap
a->data = 10;                      // asignar dato (-> es shortcut de (*a).data)
a->next = nullptr;                 // por ahora no hay siguiente

Node* b = new Node();              // crear nodo b en el heap
b->data = 20;                      // asignar dato
b->next = nullptr;                 // ultimo nodo

a->next = b;                       // enlazar: a apunta a b
cout << a->next->data;             // imprime 20 — seguir el puntero al siguiente nodo

El operador -> : ptr->campo es equivalente a (*ptr).campo. Desreferencia el puntero y accede al campo en un solo paso.

Doble puntero (para modificar head):

// Funcion que inserta al inicio de la lista
void insertFront(Node** head, int val) {   // head es puntero a puntero
    Node* nuevo = new Node();               // crear nuevo nodo en el heap
    nuevo->data = val;                      // asignar el valor
    nuevo->next = *head;                    // nuevo apunta al antiguo primero
    *head = nuevo;                          // head ahora apunta al nuevo nodo
}

// Uso:
Node* lista = nullptr;                      // lista vacia
insertFront(&lista, 5);                     // pasar la DIRECCION de lista
insertFront(&lista, 10);                    // ahora lista: 10 -> 5 -> nullptr

Se necesita Node** porque queremos modificar el puntero head en si, no solo el nodo al que apunta. Si usaramos Node*, la modificacion seria local (copia).

2.6 Paso por valor vs por referencia vs por puntero

void porValor(int x) {            // copia de x — el original NO cambia
    x = 99;                        // modifica la copia local
}

void porReferencia(int& x) {      // referencia al original — SI cambia
    x = 99;                        // modifica directamente el original
}

void porPuntero(int* x) {         // puntero al original — SI cambia (via dereferencia)
    *x = 99;                       // modifica el valor en la direccion que x contiene
}

int main() {
    int a = 1, b = 1, c = 1;      // tres variables con valor 1
    porValor(a);                   // a sigue siendo 1 (se paso una copia)
    porReferencia(b);              // b ahora es 99 (se paso una referencia)
    porPuntero(&c);                // c ahora es 99 (se paso su direccion)
    return 0;                      // a=1, b=99, c=99
}

Cuando usar cada uno:

• Valor: tipos pequenos (int, char) que no necesitas modificar
• Referencia: cuando quieres modificar el original, o para evitar copias costosas (const string&)
• Puntero: cuando necesitas nullable, reasignable, o trabajas con memoria dinamica

2.7 Trampas de punteros (errores fatales en examen)

1. Dangling pointer — usar puntero despues de delete:

int* p = new int(42);          // p apunta a memoria valida
delete p;                      // liberar memoria
cout << *p;                    // ERROR: comportamiento indefinido — memoria ya liberada

2. Memory leak — olvidar hacer delete:

void leak() {
    int* p = new int(42);      // asignar memoria en heap
}                              // p se destruye (era local) pero la memoria sigue ocupada — leak

3. Double free — hacer delete dos veces:

int* p = new int(42);          // asignar memoria
delete p;                      // liberar — ok
delete p;                      // ERROR: double free — crash o corrupcion

4. Wild pointer — puntero sin inicializar:

int* p;                        // p contiene basura — apunta a memoria aleatoria
*p = 42;                       // ERROR: escribir en direccion desconocida — crash

5. Null dereference — desreferenciar nullptr:

int* p = nullptr;              // p no apunta a nada
*p = 42;                       // ERROR: segmentation fault — crash garantizado

6. Shallow vs deep copy — copiar puntero copia la direccion, no los datos:

int* a = new int(42);          // a apunta a 42
int* b = a;                    // b apunta a la MISMA direccion que a — no es una copia del dato
*b = 99;                       // cambia el valor — ahora *a tambien es 99
delete a;                      // libera la memoria
// b ahora es dangling — apunta a memoria liberada

7. Retornar puntero a variable local — dangling instantaneo:

int* mala() {
    int x = 42;                // x vive en el stack de esta funcion
    return &x;                 // retornar direccion de variable local
}                              // x se destruye aqui — el puntero retornado es dangling

8. delete vs delete[] — usar el incorrecto:

int* arr = new int[10];        // arreglo de 10 enteros en el heap
delete arr;                    // ERROR: deberia ser delete[] arr — comportamiento indefinido

9. Array decay — pasar arreglo a funcion pierde el tamano:

void f(int* arr) {             // arr es solo un puntero — no sabe el tamano
    cout << sizeof(arr);       // imprime 8 (tamano del puntero, no del arreglo)
}
int x[100];                    // arreglo de 100 enteros
f(x);                          // se pierde la informacion de tamano al pasar

10. Off-by-one con punteros:

int arr[5] = {1,2,3,4,5};     // indices validos: 0 a 4
int* p = arr + 5;              // apunta UNA posicion despues del ultimo — no desreferenciar
cout << *p;                    // ERROR: fuera de limites — comportamiento indefinido

2.8 Smart pointers (mencion breve)

En C++ moderno se prefiere usar smart pointers en lugar de new/delete manuales:

#include <memory>                              // necesario para smart pointers

unique_ptr<int> p1 = make_unique<int>(42);     // un solo dueno — se libera automaticamente
// No se puede copiar, solo mover

shared_ptr<int> p2 = make_shared<int>(42);     // multiples duenos — cuenta referencias
shared_ptr<int> p3 = p2;                       // p2 y p3 apuntan al mismo dato — ref count = 2
// Se libera cuando el ultimo shared_ptr se destruye (ref count llega a 0)

unique_ptr es el reemplazo directo de new/delete. shared_ptr usa conteo de referencias y se libera automaticamente cuando el ultimo dueno se destruye. Para el curso usamos punteros crudos, pero saber que existen es importante.

3. Listas / Pilas / Colas

4. Ordenamiento

4.1 Traza: Merge Sort

4.2 Traza: Quick Sort (un paso de particion)

Paso a paso (Lomuto, pivote = arr[0] = 35):
i = posicion del ultimo menor encontrado
[35, 10, 65, 20, 45, 15, 50]   j=1: 10<35 → swap arr[1],arr[1] → i=1
[35, 10, 65, 20, 45, 15, 50]   j=2: 65≥35 → nada
[35, 10, 20, 65, 45, 15, 50]   j=3: 20<35 → swap arr[2],arr[3] → i=2
[35, 10, 20, 65, 45, 15, 50]   j=4: 45≥35 → nada
[35, 10, 20, 15, 45, 65, 50]   j=5: 15<35 → swap arr[3],arr[5] → i=3
Poner pivote en su lugar: swap arr[0] con arr[i=3]
[15, 10, 20, 35, 45, 65, 50]
↑ pivote en posicion final
Resultado: [15, 10, 20] | 35 | [45, 65, 50]
todos < 35         todos ≥ 35

4.3 Merge Sort — Codigo C++

// Merge: combinar dos mitades ordenadas — O(n) donde n = r - l + 1
void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> L(arr.begin()+l, arr.begin()+m+1);   // copiar mitad izquierda [l..m]
    vector<int> R(arr.begin()+m+1, arr.begin()+r+1);  // copiar mitad derecha [m+1..r]
    int i = 0, j = 0, k = l;                          // i=indice L, j=indice R, k=posicion en arr original
    while (i < L.size() && j < R.size())               // mientras ambas mitades tengan elementos
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++]; // elegir el menor de ambos frentes (<=: estable)
    while (i < L.size()) arr[k++] = L[i++];           // copiar sobrantes de L (R ya se agoto)
    while (j < R.size()) arr[k++] = R[j++];           // copiar sobrantes de R (L ya se agoto)
}
// Merge Sort — O(n log n) siempre, usa O(n) memoria extra
void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;                // caso base: subarreglo de 0 o 1 elemento ya esta ordenado
    int m = l + (r - l) / 2;          // punto medio (evita overflow vs (l+r)/2)
    mergeSort(arr, l, m);             // ordenar mitad izquierda recursivamente
    mergeSort(arr, m + 1, r);         // ordenar mitad derecha recursivamente
    merge(arr, l, m, r);             // combinar ambas mitades ordenadas en una sola
}

5. Recursion y Teorema Maestro

6. Matrices

7. Tablas Hash

7.1 Traza: Hash con Linear Probing

Insert 22: h(22)=22%7=1  → slot 1 libre      → tabla[1]=22
Insert  9: h(9) = 9%7=2  → slot 2 libre      → tabla[2]=9
Insert 30: h(30)=30%7=2  → slot 2 ocupado (9)
slot 3 libre      → tabla[3]=30
Insert 16: h(16)=16%7=2  → slot 2 ocupado (9)
slot 3 ocupado (30)
slot 4 libre      → tabla[4]=16
Insert 37: h(37)=37%7=2  → slots 2,3,4 ocupados
slot 5 libre      → tabla[5]=37
Tabla final:
[0]  [1]  [2]  [3]  [4]  [5]  [6]

22    9   30   16   37    -
Buscar 16: h(16)=2 → check 2(9≠16), 3(30≠16), 4(16=16) ✓
Buscar 11: h(11)=4 → check 4(16≠11), 5(37≠11), 6(vacio) → no existe

8. Heaps y Colas de Prioridad

8.1 Traza: Heap Insert + ExtractMax

8.2 Heap — Codigo C++

// Percolate down (max-heap) — O(log n)
// Hunde un nodo hasta que cumpla propiedad de heap (padre >= hijos)
void percolateDown(vector<int>& heap, int i, int n) {
    while (true) {
        int largest = i, l = 2*i+1, r = 2*i+2;       // hijos izq y der en arreglo
        if (l < n && heap[l] > heap[largest]) largest = l;  // hijo izq es mayor que padre?
        if (r < n && heap[r] > heap[largest]) largest = r;  // hijo der es aun mayor?
        if (largest == i) break;                       // padre ya es el mayor: propiedad cumplida
        swap(heap[i], heap[largest]);                  // intercambiar padre con el hijo mayor
        i = largest;                                   // continuar hundiendo desde la nueva posicion
    }
}

// Percolate up (max-heap) — O(log n)
// Sube un nodo hasta que su padre sea mayor (usado al insertar)
void percolateUp(vector<int>& heap, int i) {
    while (i > 0) {                                    // mientras no sea la raiz
        int parent = (i - 1) / 2;                     // indice del padre en arreglo
        if (heap[i] <= heap[parent]) break;            // padre ya es mayor: propiedad cumplida
        swap(heap[i], heap[parent]);                   // subir el nodo intercambiandolo con su padre
        i = parent;                                    // continuar subiendo desde la posicion del padre
    }
}

// Insertar en max-heap — O(log n)
void insert(vector<int>& heap, int val) {
    heap.push_back(val);                               // agregar al final (siguiente posicion libre)
    percolateUp(heap, heap.size() - 1);                // subir hasta restaurar propiedad de heap
}

// Extraer el maximo (raiz) — O(log n)
int extractMax(vector<int>& heap) {
    int maxVal = heap[0];                              // guardar el maximo (siempre en la raiz)
    heap[0] = heap.back();                             // mover ultimo elemento a la raiz
    heap.pop_back();                                   // eliminar la posicion duplicada del final
    percolateDown(heap, 0, heap.size());               // hundir la nueva raiz hasta su lugar correcto
    return maxVal;                                     // retornar el maximo que extrajimos
}

// buildHeap — O(n), NO O(n log n)
// Convierte arreglo arbitrario en heap desde abajo hacia arriba
void buildHeap(vector<int>& heap) {
    for (int i = heap.size()/2 - 1; i >= 0; i--)      // desde el ultimo padre hasta la raiz (hojas ya cumplen)
        percolateDown(heap, i, heap.size());           // corregir cada subarbol de abajo hacia arriba
}

9. Arboles Binarios y Recorridos

9.1 Recorridos — Codigo C++

// Estructura base de un nodo de arbol binario
struct TreeNode {
    int val;                        // dato almacenado en el nodo
    TreeNode *left, *right;         // punteros a hijos izquierdo y derecho (nullptr si no tiene)
};

// Todos los recorridos son O(n) — visitan cada nodo exactamente una vez

// Preorden (NLR): procesar nodo ANTES de sus hijos — util para copiar/serializar arbol
void preorder(TreeNode* n)  { if (!n) return; cout << n->val << " "; preorder(n->left); preorder(n->right); }
// Inorden (LNR): procesar nodo ENTRE hijos — en BST produce datos en orden ascendente
void inorder(TreeNode* n)   { if (!n) return; inorder(n->left); cout << n->val << " "; inorder(n->right); }
// Postorden (LRN): procesar nodo DESPUES de hijos — util para liberar memoria / evaluar expresiones
void postorder(TreeNode* n) { if (!n) return; postorder(n->left); postorder(n->right); cout << n->val << " "; }

10. BST (Arbol Binario de Busqueda)

10.1 Traza: Construir BST

10.2 BST — Codigo C++

// Insertar en BST — O(log n) promedio, O(n) peor caso (arbol degenerado)
BSTNode* insert(BSTNode* root, int key) {
    if (!root) return new BSTNode(key);                    // arbol vacio: crear nodo hoja aqui
    if (key < root->key) root->left = insert(root->left, key);   // menor: buscar lugar en subarbol izquierdo
    else if (key > root->key) root->right = insert(root->right, key); // mayor: buscar en subarbol derecho
    return root;                                           // duplicados se ignoran (no se insertan)
}

// Eliminar de BST — O(h), maneja los 3 casos clasicos
BSTNode* remove(BSTNode* root, int key) {
    if (!root) return nullptr;                             // clave no encontrada: nada que eliminar
    if (key < root->key) root->left = remove(root->left, key);   // buscar en izquierda
    else if (key > root->key) root->right = remove(root->right, key); // buscar en derecha
    else {                                                 // encontrado: eliminar este nodo
        if (!root->left) { auto t = root->right; delete root; return t; }  // caso 1/2: sin hijo izq, reemplazar con derecho
        if (!root->right) { auto t = root->left; delete root; return t; }  // caso 2: sin hijo der, reemplazar con izquierdo
        BSTNode* succ = root->right;          // caso 3 (dos hijos): buscar sucesor inorden
        while (succ->left) succ = succ->left; // sucesor = menor del subarbol derecho (ir a la izq hasta el fondo)
        root->key = succ->key;                // copiar valor del sucesor al nodo actual
        root->right = remove(root->right, succ->key); // eliminar el sucesor de su posicion original
    }
    return root;                                           // retornar raiz (posiblemente modificada)
}

// Busqueda en BST — O(h): h=log n balanceado, h=n degenerado
BSTNode* search(BSTNode* root, int key) {
    if (!root || root->key == key) return root;            // no existe o encontrado
    if (key < root->key) return search(root->left, key);  // menor: solo puede estar a la izquierda
    return search(root->right, key);                       // mayor: solo puede estar a la derecha
}

11. Arboles AVL

11.1 Traza: AVL con rotacion

11.2 AVL — Codigo C++

// Helpers — O(1): obtener altura y factor de balance de forma segura (nullptr = 0)
int height(AVLNode* n) { return n ? n->height : 0; }          // altura del nodo (0 si nulo)
int bf(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; } // BF = h(izq) - h(der)

// Rotacion simple derecha (caso LL) — O(1)
// z esta desbalanceado a la izquierda, su hijo izq (y) sube a reemplazarlo
AVLNode* rotateRight(AVLNode* z) {
    AVLNode* y = z->left;                 // y = hijo izquierdo que va a subir
    z->left = y->right; y->right = z;    // el hijo derecho de y pasa a ser hijo izquierdo de z
    z->height = 1 + max(height(z->left), height(z->right));  // recalcular z primero (ahora es hijo)
    y->height = 1 + max(height(y->left), height(y->right));  // luego y (ahora es padre)
    return y;                             // y es la nueva raiz del subarbol
}
// Rotacion simple izquierda (caso RR) — O(1), espejo de rotateRight
AVLNode* rotateLeft(AVLNode* z) {
    AVLNode* y = z->right;               // y = hijo derecho que va a subir
    z->right = y->left; y->left = z;     // el hijo izquierdo de y pasa a ser hijo derecho de z
    z->height = 1 + max(height(z->left), height(z->right));  // recalcular alturas desde abajo
    y->height = 1 + max(height(y->left), height(y->right));
    return y;                             // y es la nueva raiz del subarbol
}
// Balancear nodo AVL — O(1): detecta tipo de desbalance y aplica rotaciones
AVLNode* balance(AVLNode* node) {
    node->height = 1 + max(height(node->left), height(node->right)); // actualizar altura
    int b = bf(node);                     // calcular factor de balance
    if (b > 1) {                          // desbalanceado a la izquierda (BF = +2)
        if (bf(node->left) < 0) node->left = rotateLeft(node->left); // LR: primero rotar hijo a la izq
        return rotateRight(node);         // LL (o segunda parte de LR): rotar nodo a la derecha
    }
    if (b < -1) {                         // desbalanceado a la derecha (BF = -2)
        if (bf(node->right) > 0) node->right = rotateRight(node->right); // RL: primero rotar hijo a la der
        return rotateLeft(node);          // RR (o segunda parte de RL): rotar nodo a la izquierda
    }
    return node;                          // BF en {-1, 0, +1}: nada que corregir
}
// Insertar en AVL — O(log n) garantizado (el balance evita degeneracion)
AVLNode* insert(AVLNode* node, int key) {
    if (!node) return new AVLNode(key);                       // caso base: crear hoja nueva
    if (key < node->key) node->left = insert(node->left, key);    // menor: insertar a la izquierda
    else if (key > node->key) node->right = insert(node->right, key); // mayor: insertar a la derecha
    return balance(node);                 // re-balancear en el camino de regreso (post-recursion)
}

12. Arboles Red-Black

13. Backtracking / MinMax / Alpha-Beta

// Patron general de backtracking — O(b^d) peor caso (b=opciones, d=profundidad)
// Explora todas las combinaciones posibles podando ramas invalidas
void backtrack(State& state, int step) {
    if (isSolution(state)) { saveSolution(state); return; }  // caso base: encontramos una solucion valida
    for (auto& choice : getChoices(state, step)) {           // probar cada opcion disponible en este paso
        if (!isValid(state, choice)) continue;               // poda: descartar opciones que violan restricciones
        applyChoice(state, choice);     // HACER: aplicar la eleccion al estado actual
        backtrack(state, step + 1);     // EXPLORAR: recursar al siguiente paso con la eleccion hecha
        undoChoice(state, choice);      // DESHACER: revertir para probar la siguiente opcion (backtrack)
    }
}

14. Heap Sort — Detalle

// Heap Sort — O(n log n) siempre, in-place (O(1) memoria extra)
// Paso 1: construir max-heap, Paso 2: extraer maximos uno a uno
void heapSort(vector<int>& arr) {
    int n = arr.size();                        // tamano del arreglo
    // Fase 1: buildHeap — O(n), convierte arreglo en max-heap
    for (int i = n/2 - 1; i >= 0; i--)        // desde ultimo nodo interno hasta raiz (hojas ya son heaps)
        percolateDown(arr, i, n);              // corregir cada subarbol de abajo hacia arriba
    // Fase 2: extraer maximos — O(n log n), n extracciones de O(log n)
    for (int i = n - 1; i > 0; i--) {         // desde el final hacia el inicio
        swap(arr[0], arr[i]);                  // mover maximo (raiz) a su posicion final ordenada
        percolateDown(arr, 0, i);              // restaurar propiedad de heap en el subarreglo reducido
    }
}

15. Grafos

Grafo no dirigido — ejemplo con 4 vertices:

Grafo dirigido — ejemplo con 4 vertices:

Representacion en memoria

Ejemplo — mismo grafo con vertices A=0, B=1, C=2, D=3:

// Representacion con lista de adyacencia — O(V + E) espacio
// Cada vertice tiene un vector con sus vecinos
#include <vector>                                   // para vector
using namespace std;                                // evitar std:: en todo

// Grafo no dirigido con lista de adyacencia
struct Graph {
    int V;                                          // numero de vertices
    vector<vector<int>> adj;                        // adj[u] = lista de vecinos de u

    Graph(int V) : V(V), adj(V) {}                  // constructor: crear V listas vacias

    void addEdge(int u, int v) {                    // agregar arista no dirigida u-v
        adj[u].push_back(v);                        // v es vecino de u
        adj[v].push_back(u);                        // u es vecino de v (bidireccional)
    }
};

// Uso:
// Graph g(4);                                      // grafo con 4 vertices (0,1,2,3)
// g.addEdge(0, 1);                                 // arista 0-1
// g.addEdge(0, 2);                                 // arista 0-2
// g.addEdge(0, 3);                                 // arista 0-3
// g.addEdge(1, 3);                                 // arista 1-3
// g.addEdge(2, 3);                                 // arista 2-3

BFS (Breadth-First Search) — Busqueda en anchura

// BFS — Busqueda en anchura — O(V + E)
// Encuentra distancias minimas desde 'start' en grafo no ponderado
#include <vector>                                   // para vector
#include <queue>                                    // para queue
using namespace std;                                // evitar std::

// Retorna vector de distancias desde 'start' (-1 si no es alcanzable)
vector<int> bfs(const vector<vector<int>>& adj, int start) {
    int V = adj.size();                             // numero total de vertices
    vector<int> dist(V, -1);                        // distancias: -1 = no visitado
    queue<int> q;                                   // cola para explorar por niveles

    dist[start] = 0;                                // distancia al inicio es 0
    q.push(start);                                  // encolar vertice inicial

    while (!q.empty()) {                            // mientras haya vertices por explorar
        int u = q.front();                          // tomar el primero de la cola
        q.pop();                                    // sacarlo de la cola
        for (int v : adj[u]) {                      // para cada vecino v de u
            if (dist[v] == -1) {                    // si v no ha sido visitado
                dist[v] = dist[u] + 1;              // distancia = distancia del padre + 1
                q.push(v);                          // encolar v para explorar sus vecinos despues
            }
        }
    }
    return dist;                                    // retornar todas las distancias
}

Traza BFS desde vertice 0:

DFS (Depth-First Search) — Busqueda en profundidad

// DFS — Busqueda en profundidad — O(V + E)
// Explora lo mas profundo posible antes de retroceder
#include <vector>                                   // para vector
using namespace std;                                // evitar std::

// DFS recursivo desde vertice u
void dfs(const vector<vector<int>>& adj,            // lista de adyacencia del grafo
         int u,                                     // vertice actual
         vector<bool>& visited,                     // registro de vertices visitados
         vector<int>& order) {                      // orden de visita (resultado)
    visited[u] = true;                              // marcar u como visitado
    order.push_back(u);                             // registrar u en el orden de visita
    for (int v : adj[u]) {                          // para cada vecino v de u
        if (!visited[v]) {                          // si v no ha sido visitado
            dfs(adj, v, visited, order);             // recursar: explorar v antes de continuar con otros vecinos
        }
    }
}

// Funcion auxiliar para iniciar DFS
vector<int> dfsTraversal(const vector<vector<int>>& adj, int start) {
    int V = adj.size();                             // numero total de vertices
    vector<bool> visited(V, false);                 // ningun vertice visitado al inicio
    vector<int> order;                              // almacenar orden de visita
    dfs(adj, start, visited, order);                // iniciar DFS desde 'start'
    return order;                                   // retornar orden de visita
}

// Deteccion de ciclos en grafo dirigido — O(V + E)
// Usa coloreo: 0=blanco(no visitado), 1=gris(en proceso), 2=negro(terminado)
#include <vector>                                   // para vector
using namespace std;                                // evitar std::

bool hasCycleDFS(const vector<vector<int>>& adj,    // lista de adyacencia
                 int u,                             // vertice actual
                 vector<int>& color) {              // color de cada vertice
    color[u] = 1;                                   // marcar u como GRIS (en proceso)
    for (int v : adj[u]) {                          // para cada vecino v de u
        if (color[v] == 1) return true;             // v es GRIS → back edge → CICLO
        if (color[v] == 0 &&                        // v es BLANCO (no visitado) y
            hasCycleDFS(adj, v, color)) return true; // recursar en v encuentra ciclo
    }
    color[u] = 2;                                   // marcar u como NEGRO (terminado)
    return false;                                   // no se encontro ciclo desde u
}

bool hasCycle(const vector<vector<int>>& adj) {
    int V = adj.size();                             // numero total de vertices
    vector<int> color(V, 0);                        // todos empiezan BLANCOS
    for (int i = 0; i < V; i++) {                   // intentar DFS desde cada vertice
        if (color[i] == 0 &&                        // si no ha sido visitado y
            hasCycleDFS(adj, i, color)) return true; // encontramos ciclo → retornar true
    }
    return false;                                   // ningun ciclo en todo el grafo
}

Traza DFS desde vertice 0 (mismo grafo que BFS):

Dijkstra — Camino mas corto en grafos ponderados

// Dijkstra — Camino mas corto desde un origen — O((V+E) log V)
// No funciona con pesos negativos. Usa min-heap (priority_queue invertida)
#include <vector>                                   // para vector
#include <queue>                                    // para priority_queue
#include <climits>                                  // para INT_MAX
using namespace std;                                // evitar std::

// Retorna distancias minimas desde 'start' a todos los vertices
vector<int> dijkstra(const vector<vector<pair<int,int>>>& adj, // adj[u] = [(vecino, peso), ...]
                     int start) {
    int V = adj.size();                             // numero total de vertices
    vector<int> dist(V, INT_MAX);                   // distancias: infinito al inicio
    // min-heap: (distancia, vertice) — ordena por distancia menor primero
    priority_queue<pair<int,int>,                   // tipo de elemento: (dist, vertice)
                   vector<pair<int,int>>,            // contenedor subyacente
                   greater<pair<int,int>>> pq;       // comparador: menor primero (min-heap)

    dist[start] = 0;                                // distancia al origen es 0
    pq.push({0, start});                            // encolar (distancia=0, vertice=start)

    while (!pq.empty()) {                           // mientras haya vertices por procesar
        auto [d, u] = pq.top();                     // extraer vertice con menor distancia
        pq.pop();                                   // removerlo de la cola
        if (d > dist[u]) continue;                  // si ya encontramos algo mejor, ignorar (lazy deletion)
        for (auto [v, w] : adj[u]) {                // para cada vecino v con peso w
            if (dist[u] + w < dist[v]) {            // si encontramos camino mas corto a v
                dist[v] = dist[u] + w;              // actualizar distancia de v (relajacion)
                pq.push({dist[v], v});              // encolar nueva distancia para explorar desde v
            }
        }
    }
    return dist;                                    // retornar todas las distancias minimas
}

Traza Dijkstra — grafo ponderado:

Tabla de complejidades — Algoritmos de grafos

16. Tabla Maestra de Ordenamiento — Estabilidad

17. Resumen de Formulas Clave

18. Errores Fatales de Examen