Grafosc++grafoslista de adyacenciamatriz de adyacencia

Introducción a Grafos

Entiende qué son los grafos, sus tipos y cómo representarlos en código

OOI Oaxaca9 de febrero de 20264 min read

¿Qué es un grafo?

Un grafo es una colección de nodos (vértices) conectados por aristas (edges). Es la forma más general de representar relaciones entre objetos.

Analogía: Piensa en un mapa de ciudades. Las ciudades son los nodos, y las carreteras son las aristas. Algunas carreteras son de un solo sentido (grafo dirigido), otras van en ambas direcciones (no dirigido).

Tipos de grafos

Tipo	Descripción	Ejemplo
No dirigido	Las aristas van en ambos sentidos	Amistades en redes sociales
Dirigido	Las aristas tienen dirección	Seguidores en Twitter
Ponderado	Las aristas tienen peso (costo)	Distancias entre ciudades
No ponderado	Todas las aristas pesan igual	Conexiones de red

Terminología

Grado de un nodo: cantidad de aristas que le llegan.
Camino: Secuencia de nodos conectados por aristas.
Ciclo: Camino que empieza y termina en el mismo nodo.
Conexo: Puedes llegar de cualquier nodo a cualquier otro.
Componente conexa: Grupo máximo de nodos mutuamente alcanzables.
Árbol: Grafo conexo sin ciclos ( $n$ nodos, $n-1$ aristas).
DAG: Grafo dirigido acíclico (Directed Acyclic Graph).

Representación 1: Lista de adyacencia ⭐

La más usada en competencias. Para cada nodo, guardamos la lista de sus vecinos.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];

int main() {
    int n, m;  // n nodos, m aristas
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);  // Quitar esta línea si es dirigido
    }

    // Imprimir vecinos del nodo 1
    cout << "Vecinos de 1: ";
    for (int v : adj[1]) cout << v << " ";

    return 0;
}

Memoria: $O(n + m)$ — eficiente.

Con pesos

vector<pair<int,int>> adj[MAXN];  // {vecino, peso}

// Leer
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});

// Recorrer
for (auto [vecino, peso] : adj[nodo]) {
    // ...
}

Representación 2: Matriz de adyacencia

Una tabla 2D donde mat[i][j] = 1 si hay arista de i a j.

int mat[1005][1005];  // Solo para n ≤ 1000

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        mat[u][v] = 1;
        mat[v][u] = 1;  // Si no dirigido
    }

    // ¿Hay arista entre 2 y 5?
    if (mat[2][5]) cout << "Sí" << endl;

    return 0;
}

Memoria: $O(n^2)$ — solo para grafos pequeños.

¿Cuál usar?

Criterio	Lista de adyacencia	Matriz de adyacencia
Memoria	$O(n + m)$ ✅	$O(n^2)$
¿Hay arista u→v?	$O(\text{grado})$	$O(1)$ ✅
Recorrer vecinos	$O(\text{grado})$ ✅	$O(n)$
Grafos grandes	✅	❌

Regla general: Usa lista de adyacencia siempre, excepto cuando $n \leq 1000$ y necesitas consultar aristas frecuentemente.

Ejemplo: leer y recorrer un grafo

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[100005];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Imprimir el grafo
    for (int i = 1; i <= n; i++) {
        cout << i << ": ";
        for (int v : adj[i]) cout << v << " ";
        cout << endl;
    }

    return 0;
}

Input:

Output:

Siguiente paso

Aprende a recorrer grafos con BFS y DFS para resolver problemas de caminos y componentes.