CP-UPV Bootcamp - Capítulo 8

Capítulo 8: Grafos

PROBLEMAS DEL CAPÍTULO

Para acceder a los problemas de este capítulo, accede con tu usuario y contraseña a cpupv.contest.codeforces.com. Si no tienes usuario y contraseña, inscríbete aquí.

Introducción

En este capítulo introduciremos el tema de los Grafos, unas estructuras de datos muy importantes, que son utilizados para representar relaciones entre elementos. El potencial de estos permite desarrollar algoritmos para encontrar los caminos más cortos entre dos puntos, representar y utilizar redes de elementos, hacer emparejamientos…

Índice de contenidos

Teoría de grafos

1. Teoría de Grafos

Con origen en el curioso problema de los puentes de Konigsberg, la teoría de grafos se basa en el uso de dos conjuntos, el de vértices y el de aristas, para representar puntos topológicos, y la conexión entre dos puntos, respectivamente. Con estos dos conjuntos, podemos ser capaces de aplicar ciertos algoritmos para resolver una gran variedad de problemas que están relacionados con la topología o la comunicación entre diferentes nodos. Ahora, analicemos más en detalle los componentes de los grafos

1.1. Vértices y aristas

Los vértices de un grafo son los nodos de los que se compone, y podemos entender las aristas como los caminos que conectan pares de vértices. Por ejemplo, si tradujésemos esto a un mapa, los nodos podrían ser las ciudades, mientras que las aristas representarían las carreteras entre las ciudades(ten en cuenta que hay carreteras que pueden actuar de salida y entrada a la misma ciudad).

1.1.1. Grado de un vértice

Aparte de las conexiones, podemos obtener más información respecto a los grafos, el grado de un vértice nos indica la cantidad de aristas que conectan ese vértice con otro, por ejemplo, si un vértice B tiene grado 2, significa que tiene dos aristas conectadas (CUIDADO: podría ser solamente una arista, lo explicaremos más adelante).

grado.drawio.svg

1.1.2. Dirigidos y no dirigidos

Las aristas de un grafo, al igual que las carreteras, pueden ser de un único sentido, o de doble sentido, o incluso pueden haber dos aristas diferentes, conectando el mismo par de vértices pero con sentidos opuestos. Teniendo este aspecto en cuenta, podemos diferenciar dos tipos de grafos, los dirigidos(las aristas tienen un sentido específico, conectan un nodo A con un nodo B, permitiendo únicamente ese mismo camino, y no en el sentido opuesto), y los no dirigidos(las aristas que conectan los pares de nodos permiten caminar en ambos sentidos).

Además, esto afecta a cómo se calcula el grado de un vértice:

Grafo dirigido: Podemos diferenciar entre grado saliente y grado entrante, dependiendo de si contamos las aristas que salen hacia otros nodos, o las que conectan otros nodos con este.
Grafo no dirigido: Ya que las aristas permiten ambos sentidos, para obtener el grado de un vértice en este tipo de grafos, solamente debemos contar las aristas que están conectando este vértice con otros.

1.1.3. Loops

Como hemos mencionado anteriormente, una arista conecta cualquier par de vértices, incluso, podemos encontrar aristas que conectan un vértice consigo mismo, esto se denomina loop, o bucle.

Los bucles nos pueden complicar en cierta manera la resolución de problemas específicos relacionados con los grafos si no son manejados de manera adecuada. Por ejemplo, en el cálculo de grados de un vértice, habíamos mencionado anteriormente que un vértice de un grafo no dirigido podía tener grado 2 aún solamente usando una arista, esto es debido a que la arista se trataba de un bucle, que incrementa el grado en 2 unidades, y no en 1.

1.2. Tipos de grafos

Además de todas las clasificaciones anteriores, los grafos pueden ser clasificados de acuerdo a varias características de estos, como vamos a ver a continuación:

1.2.1. Subgrafo

Partiendo de que un grafo es un conjunto no vacío de vértices y otro conjunto de aristas, podemos en realidad obtener subgrafos de este subgrafo, siempre y cuando los conjuntos que escojamos tengan sentido. Por ejemplo, en un grafo 3 → 4 → 11 → 3, podemos obtener un subgrafo formado por 4 → 11, este subgrafo siempre deberá contener nodos y aristas del grafo principal, ya que, de no ser así, se trataría de un grafo diferente al previamente mencionado.

1.2.1.1. Componentes, conexos e inconexos

En ciertas ocasiones, nos podremos encontrar que un grafo está dividido en varios componentes, esto es, en varios subgrafos que no están conectados entre sí por ninguna arista, como por ejemplo puede ser el grafo: 3 → 4 → 5 1→ 2

3 → 4 → 5 es un componente (donde 3, 4 y 5 son nodos conexos entre ellos) y 1 → 2 es otro diferente(1 y 2 están conexos entre sí) pero al no haber arista conectando ambos componentes, los componentes no están conexos, por lo que el grafo en sí no es conexo.

El grafo es inconexo

Dicho esto, podemos añadir otro criterio de clasificación de los grafos, dependiendo de si son conexos o no, si están formados por un solo componente o más de uno, respectivamente.

imagen: 1 → 2 → 3 → 4 → 5 es conexo

El grafo es conexo

El hecho de que los grafos puedan ser conexos o no debe ser considerado cuando estamos tratando de resolver cierto problema. Por ejemplo, no podríamos obtener el camino de 3 a 1 en el primer caso, mientras que en el segundo sí que sería posible.

💡 Hemos de tener en cuenta también la accesibilidad en los grafos dirigidos, esto es, si un nodo se puede visitar desde otro nodo. Por ejemplo, el nodo 2 es accesible por todos los otros nodos, en cambio, el 3 no es accesible desde el nodo 1, ya que no existe arista que permita ese camino. Esto se puede observar con la dirección de las aristas.

1.2.2. Árboles

Ahora pasamos a la clasificación de los grafos de acuerdo a la conexión entre los nodos de un grafo, comenzando con los árboles. Los árboles son grafos que cumplen ciertas características especiales, que son:

Es un grafo no dirigido
Para cada par de vértices, existe un único camino que los conecta
No contiene loops
Es conexo

Podemos ver que todas esas características se cumplen en el ejemplo dado.

Profundizando más en los árboles, también nos podemos dar cuenta de que además, todos los árboles tienen, dados n vértices, n - 1 aristas, pero CUIDADO: no todos los grafos con n - 1 aristas son árboles

Aún teniendo n-1 aristas, al no ser conexo, no es un árbol

Además, podemos distinguir dos tipos de vértices en los árboles, los nodos internos y las hojas, dependiendo de si tienen grado mayor que 1, o grado 1, respectivamente.

Los árboles son un tipo especial de grafo que tiene una gran variedad de usos y tipos. Un ejemplo muy reciente de su utilidad es en la snapshot 23w34a de Minecraft, que basándose en un octree, han conseguido optimizar considerablemente la carga de chunks cuando la distancia de renderizado es elevada, mejorando notablemente la experiencia al jugar.

1.2.3. Simples

Los grafos simples son caracterizados por:

No tener bucles
Para cada par de vértices conexos solamente existe una arista conectándolos

Entender cómo se pueden aplicar ciertos algoritmos y técnicas a grafos simples nos puede ayudar a extender o adaptar estos a grafos más complejos, además de ser capaces de representar problemas mediante grafos, como por ejemplo una “red social”.

1.2.4. Completos

Los grafos completos son caracterizados por:

No tener bucles
Todos los nodos tienen exactamente una arista conectando a cada uno del resto de nodos
Teniendo n vértices, tiene \(\frac{n(n-1)}{2}\) aristas

Como podemos observar, los grafos simples en realidad son un subconjunto dentro de los grafos completos, siendo los grafos simples en los que no es necesario que todos los nodos tengan una arista conectando al resto de nodos.

Los grafos completos nos pueden ser útiles debido a que tienen la máxima densidad posible, de esta forma, podemos probar algoritmos y sus casos extremos, o también representar problemas relacionados con combinatoria, debido a la naturaleza de este tipo de grafos.

1.2.5. Bipartitos

Los grafos bipartitos también tienen una serie de características especiales:

No contiene bucles
Se puede dividir en dos conjuntos, en los que cada nodo de un conjunto solamente puede tener aristas conectando directamente a nodos del otro conjunto

Los grafos bipartitos pueden ser útiles para solucionar varios tipos de problemas, algunos más complejos como el del matrimonio estable, y permiten aplicar algoritmos como el de Ford-Fulkerson, para obtener el flujo maximal.

1.3. Caminos

Existen diferentes formas de explorar un grafo, dependiendo de si los vertices y aristas se pueden revisitar, y dependiendo también de si buscamos encontrar una ruta que cumpla ciertas características, veremos eso a continuación.

1.3.1. Camino (walk)

Un camino dentro de un grafo se puede definir como una secuencia finita que alterna vértices y aristas, no importa si volvemos a visitar un vértice o una arista, ni si acabamos en el mismo punto que el de inicio.

Además, de un camino podemos obtener su longitud, siendo esta la cantidad de aristas visitadas. En el caso de un camino de longitud 0, nos hemos encontrado con un camino trivial.

1.3.2. Recorrido (trail)

En un recorrido, la diferencia que podemos encontrar respecto a los caminos, es el hecho de que no podemos revisitar ninguna arista.

1.3.3. Camino simple (path)

En un camino simple, no podemos revisitar ningún vértice ni arista, tampoco es posible cerrar el camino acabando en el mismo vértice con el que hemos comenzado.

Un caso muy común en el que trataremos de encontrar un path sería la búsqueda de un camino para llegar de un punto a otro de un mapa, como por ejemplo salir de un laberinto.

1.3.4. Ciclo

Un ciclo es bastante similar a un camino simple, pero siendo necesario en este caso terminar en el mismo vértice con el que se ha comenzado.

1.3.4.1. Ciclo euleriano

Siendo el ciclo que se buscaba encontrar en el problema de los puentes de Königsberg, un ciclo euleriano es aquel que recorre todas y cada una de las aristas una única vez, para acabar en el mismo vértice con el que se ha comenzado.

Para identificar si un grafo contiene un ciclo euleriano, debemos tener en cuenta que se deben cumplir estas características:

El grafo debe ser conexo y no dirigido
Todos los vértices tienen grado par

El ciclo euleriano se puede utilizar en problemas en los que se trata de averiguar si todo un conjunto de opciones se puede cubrir en su totalidad o no, por ejemplo, un problema en el que tengamos que averiguar si existe una ruta que cubra todas las calles de un mapa, como es el Problema del Cartero Chino.

1.3.4.2. Ciclo hamiltoniano

Cuando hablamos de un ciclo hamiltoniano, la principal diferencia que existe respecto al ciclo euleriano, es que en este caso en vez de tener que visitar todas las aristas existentes en el grafo, se han de visitar todos los vértices, y acabar exactamente en el mismo vértice con el que se ha comenzado el ciclo.

Las condiciones necesarias(pero no suficientes) para que se de un ciclo hamiltoniano son:

El grafo ha de ser conexo
Todos los vértices deben tener grado > 1

Aparte de estas dos condiciones, si queremos asegurarnos de que un grafo contiene un ciclo hamiltoniano, podemos utilizar el Teorema de Dirac, que establece que:

Si \(G\) es un grafo conexo, simple y sin lazos con \(n\) vértices, con \(n \ge 3\), en el cual \(grado(u) + grado(v) ≥ n\) para todo par de vértices no adyacentes \(u\), \(v\), entonces \(G\) es hamiltoniano.

Como curiosidad, el hallar un ciclo hamiltoniano en un grafo es caracterizado como un problema NP-Completo, y de hecho, está incluido en la lista de los 21 Problemas NP-Completos de Karp, una colección de problemas muy famosa creada por el informático teórico Richard Karp.

2. Cómo trabajar con grafos

Ahora llegamos a la parte más interesante de este capítulo, veremos las dos formas en las que se puede trabajar con grafos, teniendo en cuenta las ventajas y desventajas de cada una de las técnicas.

2.1. Listas de adyacencia

La forma más común de representar grafos es mediante listas de adyacencia, de manera que, formaremos una lista ordenada con todos los vértices del grafo, y en cada entrada de esta lista, se hallará otra lista que contienen los vértices adyacentes al vértice con el que se corresponde la entrada. Por ejemplo:

De este grafo, podemos obtener la siguiente lista de adyacencia:

a -> b -> c -> d
b -> a -> c
c -> a -> b
d -> a

Entonces, para poder explorar o cambiar de vértices en un grafo, lo que haremos será cambiar nuestro “puntero” o elemento al que estamos apuntando, por uno de los adyacentes a este. Por ejemplo, si empezamos en el vértice c, para alcanzar el vértice d debemos repetir estos dos pasos hasta llegar al punto deseado:

Obtener lista de adyacentes
Seleccionar el adyacente que nos convenga en cada ocasión(existen varias estrategias de seleccionar el adyacente y explorar un grafo, las veremos a continuación)

Ahora, para pasar esto a código, podemos basarnos también en listas, como pueden ser los vector de C++.

void addEdge(vector<vector<pair<int, int>>> &graph, int i, int j, int weight) {
    // Considerando grafo no dirigido
    graph[i].push_back(make_pair(j, weight));
    graph[j].push_back(make_pair(i, weight));
}

void removeEdge(vector>> &graph, int i, int j) {
	for (int idx = 0; idx < graph[i].size(); idx++) {
        if (graph[i][idx] == j) {
            graph[i].erase(graph[i].begin() + idx);
            break;
        }
    }
	for (int idx = 0; idx < graph[j].size(); idx++) {
        if (graph[j][idx] == i) {
            graph[j].erase(graph[j].begin() + idx);
            break;
        }
    }
}

void main() {
    vector<vector<pair<int, int>>> graph;
    addEdge(graph, a, b, 1);
    addEdge(graph, a, c, 1);
    addEdge(graph, b, c, 1);
    addEdge(graph, a, d, 1);	
}

El hecho de que en general siempre se usen listas de adyacencia para representar grafos se debe a las varias ventajas que esta técnica posee:

Ocupa poca memoria al almacenar solamente el vértice de destino(aunque podemos añadir pesos si es necesario)
Eficiente para la implementación de los algoritmos más usados en grafos, como lo son el BFS y el DFS.
Permite modificar eficientemente el grafo modificando solamente la adyacencia que deseemos

2.2. Matriz de adyacencia

La matriz de adyacencia representa la posible conexión entre todos los vértices del grafo, incluyendo bucles, mediante una matriz \(A\) de tamaño \(n \times n\). En esta matriz, cada columna \(i\) representa el vértice de inicio, mientras que cada fila \(j\) representa el vértice de destino, de forma que cada intersección \(A_{ij}\) tiene un valor de \(1\) o \(0\), dependiendo de si existe una arista conectando el vértice \(i\) con el vértice \(j\) o no.

Reutilizando el mismo grafo que en el apartado anterior, la matriz de adyacencia quedaría de la siguiente forma:

	a	b	c	d
a	0	1	1	1
b	1	0	1	0
c	1	1	0	0
d	1	0	0	0

Curiosamente, si utilizamos un grafo no dirigido, la matriz resultante será simétrica. En cambio, si representamos un grafo dirigido, como el siguiente:

Se nos queda una matriz de adyacencia como esta:

	a	b
a	0	0
b	1	0
c	1	1
d	1	0

Traduciendo esto a código:

int numVertices;
bool adjMatrix[numVertices][numVertices];

void addEdge(int i, int j) {
    adjMatrix[i][j] = true;
    
    // Esta linea se eliminaría para grafos dirigidos
    adjMatrix[j][i] = true;
}

void addEdge(int i, int j) {
    adjMatrix[i][j] = false;
    
    // Esta también
    adjMatrix[j][i] = false;
}

void main() {
    addEdge(a, b);
    addEdge(a, c);
    addEdge(b, c);
    addEdge(a, d);
}

Usar una matriz de adyacencia nos da ventajas como:

Añadir, eliminar o verificar adyacencias se puede hacer en tiempo constante.
Nos permite saber sobre la naturaleza del grafo realizando una serie de operaciones matriciales.
Aprovecha mejor el espacio si el grafo es altamente denso

2.3. Algoritmos y operaciones

Ahora que ya sabemos representar grafos, es hora de ponerse manos a la obra y practicar cómo podemos explorar, modificar y utilizar grafos para resolver los problemas a los que nos enfrentamos.

Dos algoritmos esenciales son el Breadth-First-Search(BFS) y el Depth-First-Search(DFS), ambos son algoritmos de búsqueda de un grafo, pero también se pueden utilizar para otros fines, como implementar otros algoritmos más avanzados.

2.3.1. BFS

Este algoritmo se basa en primero explorar, siguiendo el orden en el que se han descubierto, los vértices adyacentes a los que hemos visitado:

void BFS(const vector<vector<int>>& adjList, int startVertex) {
    vector<bool> visited(adjList.size(), false);
    queue<int> q;

    visited[startVertex] = true;
    q.push(startVertex);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        cout << "Visited: " << vertex << endl;

        for (int neighbor : adjList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

Para la aplicación de este algoritmo, primero necesitaremos ciertas estructuras de datos auxiliares, que serán en este caso, una lista para saber qué vértices ya se han visitado, y una cola en la que iremos añadiendo los vértices adyacentes en el orden que son encontrados. Una vez inicializadas estas dos estructuras, seguimos el siguiente proceso:

Visitamos el vértice en la cola, no sin antes especificar que ese vértice se ha visitado
Obtenemos la lista de vértices adyacentes, y los añadimos a la cola
Repetir visitando el siguiente vértice en cola

Algunas de las ventajas que nos proporciona este algoritmo son la simplicidad de implementación y su eficiencia para la exploración de grafos amplios pero poco profundos. Mientras que entre los usos de este algoritmo, podrían estar la detección de ciclos, la búsqueda de todos los vértices a cierta distancia, o la “difusión” a través del grafo.

2.3.2. DFS

Por otra parte, el DFS en vez de explorar “por niveles”, se centra en explorar cada ramificación hasta el final, para después explorar las próximas ramificaciones que se encuentra en el camino de vuelta.

void DFSUtil(int vertex, const vector<vector<int>>& adjList, vector<bool>& visited) {
    // Marca el vértice como visitado
    visited[vertex] = true;
    
    // Itera sobre los vértices adyacentes
    for (int neighbor : adjList[vertex]) {
        if (!visited[neighbor]) {
            DFSUtil(neighbor, adjList, visited);
        }
    }
}

void DFS(const vector<vector<int>>& adjList, int startVertex) {
    vector<bool> visited(adjList.size(), false);
    DFSUtil(startVertex, adjList, visited);
}

El DFS, de manera similar al BFS, también utiliza una lista auxiliar para registrar los vértices visitados. El algoritmo sigue los siguientes pasos:

Visita el vértice y marca como visitado
Obtén adyacentes del vértice
Explorar la ramificación hasta el final
Si hay más ramificaciones, explorarlas también. Si no es el caso, volver hacia atrás hasta la próxima ramificación.

El Depth-First-Search posee la ventaja de utilizar los recursos de manera más eficiente al aprovecharse del propio stack de la recursión, además de ser útil para algoritmos de búsqueda de caminos y detección de ciclos o componentes conexos.

3. Dijkstra

El algoritmo de Dijsktra es posiblemente el algoritmo más famoso relacionado con Teoría de Grafos, dado que este es capaz de calcular el camino más corto de un punto a otro del grafo de una manera notablemente eficiente.

Los pasos a seguir de este algoritmo son:

Inicializamos estructuras auxiliares
1. Array dist[n], que almacena la menor distancia encontrada desde el vértice inicial hasta ese vértice. dist[source] = 0, y el resto a INT_MAX
2. Cola de prioridad para almacenar las aristas, dando más prioridad a la arista más corta.
3. Array visited[], que tiene la misma finalidad que en los otros algoritmos mencionados previamente. Y es que, en realidad, Dijsktra se puede implementar utilizando de base el DFS o el BFS.
Comenzamos con el vértice origen y buscaremos el arista de menor peso conectado a este vértice, marcándolo como visitado.
Obtenemos el siguiente elemento de la cola de prioridad, en el cual repetiremos el paso 2
Visitaremos el nodo nuevo, cambiando el array dist[] si fuese necesario
Añadir vértices adyacentes a la cola de prioridad.
Repetir paso 2

void dijkstra(int source, const vector<vector<pii>>& adj, vector<int>& dist) {
    int V = adj.size(); // vértices en el grafo

    // Cola de prioridad
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    // Inicializa distances all vertices as infinite
    dist.assign(V, std::numeric_limits<int>::max());
    dist[source] = 0; // Distancia al nodo origen es 0
    pq.push({0, source});

    // Procesa la cola de propiedad
    while (!pq.empty()) {
        int u = pq.top().second; // Get the vertex with the smallest distance
        int d = pq.top().first;  // Get the distance of the vertex
        pq.pop(); // Remove the vertex from the priority queue

        // Skip processing if the distance is not optimal (stale entry)
        if (d > dist[u]) continue;

        // Traverse all neighbors of the vertex u
        for (const auto& edge : adj[u]) {
            int v = edge.first;    // Neighbor vertex
            int weight = edge.second; // Edge weight

            // Relaxation step: update the distance if a shorter path is found
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v}); 
            }
        }
    }
}

A pesar de la conveniencia de este algoritmo, no todo puede ser perfecto, y es que si el grafo al que nos enfrentamos posee aristas de peso negativo, no podemos usar este algoritmo. Sin embargo, existe una alternativa al algoritmo de Dijsktra, el algoritmo de Bellman-Ford, que si que es capaz de superar ese obstáculo.

Además, si se da el caso de que queremos calcular el camino más corto desde cada vértice del grafo a cualquier otro vértice, en vez de aplicar Dijsktra por cada vértice, podemos utilizar otro conocido algoritmo, el algoritmo de Floyd-Warshall, que utiliza la programación dinámica y la matriz de adyacencia para calcular dichos caminos.