Un grafo es un conjunto de vertices(V) y aristas(E).
El conjunto de aristas de un grafo (E) debe estar contenido en el conjunto generado por la operación V×V siendo esta el producto de todos los vértices del grafo: E⊆V×V
📖
La complejidad de los algoritmos sobre grafos suele medirse en función de…
Número de vértices: ∣V∣=n
Número de aristas: ∣E∣=n
💡
Cuando analizamos la complejidad en función de estos parámetros, no incluiremos las barrras verticales. Ejm.: O(V) en lugar de O(∣V∣)
🎨
Las representaciones más usadas para representar grafos son:Lista de adyacencias
Características
Representación compacta para grafos dispersos(con pocas aristas respecto del número de vérices: (∣E∣<<∣V∣2))
El acceso a los datos no es constantes (puede llegar a ser lento)
Matriz de adyacencias
Características
La memoria utilizada es fija Θ(V2), no depende de la densidad del grafo
Cuando el grafo es poco denso, se desperdicia memoria
Cuando el grafo es muy denso, no se desperdicia memoria
El acceso a memoria es constante
Tipos de Recorridos
Recorrido en profundidad
⏬
El recorrido en profindidad o Depth-First Search (DFS) se basa en el criterio principal de:
Visitar los vertices hijos antes que los hermanos
💡
Este algoritmo se suele implementar de forma recursiva, incluyendo un lista de nodos visitados para evitar una recursión infinita. También se puede implementar de forma iterativa si se usa una pila para anotar los siguientes nodos que debemos visitar
📟
Pseudo-códigoFunción iniciadora
Si estuvieramos seguros de que el grafo es conexo, entonces esta función solo inicializaría las estructuras de datos y llamaría a la función recursiva una vez. Pero como no podemos estar seguros de eso, entonces hay que llamar a la función recursiva una vez para cada vértice con un bucle for
procedimiento
Función recursiva
En este caso, el algoritmo marcará como visitado el nodo actual. A continuación recorrerá todos sus hijos, y para cada uno de ellos que no esté visitado, hará una llamada recursiva
procedimiento
🧠
La complejidad del algoritmo visto anteriormente sería la siguiente….
Si cada vértice se visita al menos una vez en la función dfs entoces la complejidad de recorrer todos los vértices es Θ(V). Dado que cada vértice se visita una única vez y una vez visitado, se recorren todas sus aristas una única vez, entonces la complejidad de recorrer todas las aristas es Θ(V). Por lo tanto la complejidad del algoritmo DFS es O(max{V,E})
💡
Conceptos
🌲 El recorrido de un grafo conexo da como resultado un arbol de recubrimiento
🌳 Si el grafo no es conexo, se obtiene un arbol por cada componente conexa (grupo/bosque)
0️⃣ La exploración en profundidad de un grado visita los nodos en preorden
El recorrido en anchura o Breadth-First Search (BFS) se basa en el criterio principal de:
Visitar los vertices los hermanos antes que los hijos de cada uno de estos
💡
Este algoritmo se suele implementar de forma iterativa, incluyendo un lista de nodos visitados para evitar una recursión infinita. Se suele implementar una cola para anotar cuales son los siguientes nodos que debemos visitar
📟
Pseudo-códigoFunción iniciadora
Inicializamos la lista de nodos visitados a no visitados. Después recorremos los nodos, y aquellos que no estén visitados, hacemos la llamada a la función recursiva
procedimiento
Función recursiva
Inicializamos la cola vacía. Ponemos el nodo raiz como visitado y lo incluimos en la cola. Luego comenzamos el bucle que no parará hasta que la cola que hemos creado no esté vaciá.
En cada ciclo del bucle se tomará el primer nodo de la cola, se pondrá a visitado, se sacará este de la cola y se introduciran todos los nodos adyacentes a este en la cola que no hayan sido visitados ya
procedimiento
🧠
La complejidad del algoritmo visto anteriormente es la misma que para el algoritmo en profundidad. Por lo tanto la complejidad del algoritmo DFS es O(max{V,E})
💡
Conceptos
🌲 El recorrido de un grafo conexo da como resultado un arbol de recubrimiento
🌳 Si el grafo no es conexo, se obtiene un arbol por cada componente conexa (grupo/bosque)
0️⃣ La exploración en profundidad de un grado visita los nodos en inorden
Ordenación Topológica
📖
Dado un grafo dirigido y acíclico, se denomina ordenación topológica a una disposición lineal de los nodos tal que, dado un arco (u,v), el nodo u esté antes que v en la ordenación
Un vertice se visita sí y solo sí se han visitado todos su predecesores
En el caso de los grafos con ciclos, el algoritmo sigue siendo válido pero la interpretación no es directa
La ordenación topológica no es única
Como realizar una ordenación topológica
🗺️
La ordenación topológica consiste en ir recorriendo el grafo siguiendo el algoritmo dfs
Cuado recorramos un nodo vamos a ir anotando dos números usando el siguiente formato: i/f siendo i y f un número que representa lo siguiente:
i → El número de paso en el que visitamos el nodo por primera vez
j → El número de paso en el que pasamos por este nodo cuando estabamos volviendo sobre nuestros pasos y no había más nodos que visitar desde el nodo actual
Finalmente, para realizar la ordenación topológica, recorreremos los nodos en orden inverso, osea, vamos apuntando los nodos de izquierda a derecha empezando por los nodos con la j más alta. Cuando escribamos un nodo, comprobaremos si tiene aristas entrante, y las representaremos. Cuando vayamos a escribir el siguiente nodo, lo conectaremos con el anterior a través de una arista
En resumen
El numero de antes de la barra es el paso en el que hemos visitado dicho nodo por primera vez
El numero de detras de la barra es el paso en el que nos hemos quedado sin nodos que visitar desde el nodo actual
Cuando nos quedamos sin nodos que visitar, nos movemos al nodo anterior (el que nos levó al nodo actual, el que tiene como número de antes de la barra el número: i−1)
Para ordenar topológicamente, escribimos en los nodos en orden descendente respecto del número de detrás de la barra y dibujaremos las aristas entrantes
💡 El primer num no te aporta nada
Ejemplo de un recorrido para una ordenación topológica
Ejemplo de ordenación topológica
Grafo con la notación pero antes de ser ordenado topológicamente
Grafo con la notación y ordenado topológicamente
Algoritmo de la ordenación topológica
ORDENACIÓN_TOPOLÓGICA
💡
La ordenación topológica también se conoce como el recorrido en postorden
Descomposición de un Grafo
🪓
Para descomponer un grafo en sus componenetes fuermentente conexas…
Aplicar la ordenación topológica sobre G
Calcular el grafo traspuesto GT
Aplicar la DFS
Otros conceptos sobre los grafos
📖
Se dice que un grafo es fuertemente conexo cuando existe un camino entre cada par de vértices del grafo
📖
Un punto de articulación es un vértice v de un grafo conexo el cual si es eliminado da lugar a un grafo no conexoCálculo de los puntos de articulación
Sea v cualquier vértice del árbol (excepto la raíz)
Si masAlto[x] < preOrden[v] implica que se puede llegar desde x a regiones más altas sin pasar por (v,u). Entonces uno es un punto de articulación
Si preOrden[x] >= masAlto[v] no se puede llegar desde u a regiones más altas del grafo sin pasar por (v,u). Entonces ues un punto de articulación
Si u es la raíz del árbol y tiene más de un hijo, es un punto de articulación
📖
Un grafo biconenxo es aque que no tiene puntos de articulación
📖
Un grafo bicoherente es aquél grafo cuyos puntos de articulación están unidos a cada uno de los subgrafos que se encuentra unidos gracias a este por, al menos, dos aristas.
