PRESENTACIÓN Busquedas de grafos

Busquedas

Por Miguel Alejandro Hernandez Trujillo.

Grafos y sus algoritmos

01

Representacion ligada de grafos dirigidos.

Representaciones de Grafos dirigidos.

Se pueden usar varias estructuras para representar un digrafo, como la matriz de adyacencia. Esta matriz de tamaño nxn contiene valores binarios; A[i][j] es 1 si hay un arco del vértice i al j y 0 si no existe. Otra opción es la matriz de adyacencia etiquetada, donde A[i][j] contiene la etiqueta del arco de i a j. Si no hay un arco, se puede usar una etiqueta especial. La elección de la estructura depende de las operaciones a realizar en el digrafo. Ejemplo: A continuación se muestra un digrafo y su correspondiente matriz de adyacencia.

Busquedas: grafos y sus algoritmos

Representaciones de Grafos dirigidos.

La matriz de adyacencia tiene una gran desventaja al requerir Ω(n^2) de memoria, incluso si el digrafo tiene menos arcos. Leer o examinar la matriz también lleva tiempo O(n^2). Para superar esto, se puede usar la lista de adyacencia como otra representación para el digrafo. La lista de adyacencia de un vértice i es una lista de todos sus vértices adyacentes, lo que permite representar el digrafo de manera más eficiente mediante un array HEAD donde HEAD[i] es un puntero a la lista de adyacencia del vértice i.

Busquedas: grafos y sus algoritmos

Ejemplo: A continuación se muestra un digrafo y su representación usando la lista de adyacencia. Se ha usado una lista enlazada simple.

Representaciones de Grafos dirigidos.

La representación mediante lista de adyacencia requiere memoria proporcional al número de vértices más el número de arcos, lo que la hace adecuada cuando el número de arcos es mucho menor que n^2. Sin embargo, determinar si hay un arco entre los vértices i y j puede tomar tiempo O(n). Si el grafo se mantiene fijo con pocos o ningún cambio en la lista de adyacencia, se puede utilizar HEAD[i] como un cursor para un array ADJ, donde ADJ[HEAD[i]] contiene los vértices adyacentes a i hasta que se encuentre un final de lista (que podría ser un 0). Esta estrategia puede mejorar la eficiencia en el acceso a los vértices adyacentes en algunos casos.

Busquedas: grafos y sus algoritmos

02

Algoritmos de grafos: búsqueda en profundidad y anchura.

¿Qué es un Algoritmo de Grafos?

Los algoritmos de grafos son un conjunto de instrucciones que recorren (visitan los nodos de) un grafo. Algunos algoritmos son usados para hallar un nodo específico o el camino entre dos nodos dados.

Busquedas: grafos y sus algoritmos

¿Por qué son Importantes los Algoritmos de Grafos?

Los grafos son estructuras de datos muy útiles que se usan para modelar varios problemas. Estos algoritmos tienen aplicaciones directas en sitios de redes sociales, modelado de máquinas de estado y más.

Algoritmos de Grafos Comunes

Algunos de los algoritmos de grafos más comunes son:

• Búsqueda en Amplitud o Anchura (Breadth First Search, BFS)
• Búsqueda en Profundidad (Depth First Search, DFS)
• Dijkstra
• Algoritmo de Floyd-Warshall

Busquedas: grafos y sus algoritmos

03

Grafos dirigidos libres de ciclos.

Busquedas: grafos y sus algoritmos

Grafo aciclico dirigido

Su uso es común cuando se desea representar relaciones de dependencia o jerarquías, como en sistemas de tareas o procesos en los que no pueden existir dependencias circulares. De manera informal, se puede decir que un DAG "fluye" en una sola dirección sin volver sobre sí mismo.

Un grafo acíclico dirigido (DAG) es un tipo de grafo dirigido que no tiene ciclos, lo que significa que no hay un camino que comience y termine en el mismo vértice. Los DAG se utilizan en ciencias de la computación y matemáticas en modelos donde no tiene sentido que un vértice tenga un camino directo a sí mismo.

Cada DAG (grafo acíclico dirigido) se relaciona con un ordenamiento parcial ≤ en sus vértices, donde u ≤ v si y solo si existe un camino directo desde u hasta v. Varios DAG pueden generar el mismo ordenamiento parcial, y el que tiene el menor número de arcos se llama reducción transitiva, mientras que el que tiene el mayor número de arcos se conoce como Clausura transitiva. Específicamente, la Clausura transitiva corresponde al orden de accesibilidad ≤.

Busquedas: grafos y sus algoritmos

terminologia

Una fuente es un vértice sin flujos (relaciones) de entrada, mientras que un sifón o sumidero es un vértice sin flujos (relaciones) de salida. Un DAG finito tiene por lo menos una fuente y un sifón. La profundidad de un vértice, en un DAG finito, es la longitud del camino más largo que existe desde una fuente a dicho vértice, la altura de un vértice es la longitud más larga del camino que exista desde el vértice a un sifón. La longitud de un DAG finito es la longitud (número de arcos) del camino directo más largo. Dicha longitud es igual a la máxima altura de todas las fuentes e igual a la máxima profundidad de todos los sifones.

Busquedas: grafos y sus algoritmos

¡GRACIAS!