El Algoritmo

Un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices. Por otro lado, y debido a su generalidad y a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo.

Para facilitar el estudio de este tipo de dato, a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia, aquí sólo se realizará una introducción a la misma, describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.

3. TAD Grafo

♦ Como tipo abstracto de dato un grafo G = (V, A) consta de un conjunto V de vértices y de un conjunto A de pares de vértices de V, llamados arcos.

♦ Esto implica la necesidad de definir dos nuevas clases llamadas Vértice y Arco. Un vértice es un objeto compuesto de una etiqueta. Un arco es un objeto compuesto de dos vértices y opcionalmente de una etiqueta.

El diseño del TAD Grafo es como sigue. Esta compuesto por una secuencia de duplas de la forma

(V; Lista), donde V es objeto del tipo vértice y Lista A dj es una secuencia de objetos del tipo Lado, que corresponden a los lados que poseen vértices que son adyacentes al vértice V. El número de duplas de la secuencia es igual al número de vértices del grafo. Cuando es un TDA Grafo No Dirigido, acada vértice V le asociamos la secuencia de aristas incidentes al vértice V. En caso de un TDA Grafo Dirigido, a cada vértice V, le asociamos la secuencia de arcos en los cuales el vértice V es el extermoinicial de los mismos. En la gura 1 se observa una representación graca del TDA Grafo.

Matriz de caminos

La matriz de caminos M indica los caminos de longitud 1 desde un vértice dado a otro, y el número de ellos. Hallando M2=M*M, tenemos los caminos de longitud 2, M3 indica los caminos de longitud 3, y así sucesivamente con los caminos 4, 5,..., n siendo n el número de vértices del grafo.

Sea G un grafo dirigido simple con m nodos v1, v2…..vm. La matriz de caminos o matriz de alcance de G es la matriz m-cuadrada P= v (i, j) definida como sigue:

P = {1 Si hay un camino desde vi hasta vi 0 en otro caso

Suponga que hay un camino desde vi hasta vi. Entonces tiene que haber un camino simple desde vi hasta vi cuando vi=vi, o un ciclo de vi a vi cuando vi=vi. Como G solo tiene m nodos n un camino simple así ha de tener longitud m-1 o menor, o un ciclo así ha de tener longitud m o menor. Esto significa que existe una entrada ji no nula de la matriz BM definida de la anterior subsección. De acuerdo con esto, tenemos la siguiente relación entre la matriz de caminos P y la matriz de adyacencia A.

Considere el grafo G con m=4 nodos de la figura 8.3 .Sumando las matrices con las potencias A,A(2),A(3) y A(4) obtenemos la siguiente matriz B4 , reemplazando las entradas positivas por 1, obtenemos la matriz de caminos P del grafo G .

Algoritmos fundamentales de grafos Búsqueda por Niveles (Breadth-First Search) 0 1 2 3 5 4 6 El algoritmo inicia examinando cada una de las aristas salientes de este nodo inicial. Se van descubriendo nuevos nodos cuando el algoritmo examina estas aristas salientes Estos nodos "descubiertos" son colocados dentro de una cola. Luego el algoritmo de búsqueda por niveles, examina cada nodo descubierto para determinar si se pueden alcanzar nuevos nodos desde el nodo descubierto Una vez que un nodo ha sido descubierto, éste es colocado dentro de una cola de nodos que han sido descubiertos, pero no explorados. Luego el algoritmo termina de explorar el nodo inicial, examinando su arista restante. Un nodo está completamente explorado cuando todas sus aristas han sido examinadas. Cuando la exploración de un nodo se completa, el algoritmo selecciona otro nodo para ser explorado El algoritmo finalmente termina cuando se queda sin nodos que requieran ser explorados. Búsqueda por Profundidad Un algoritmo búsqueda por profundidad (depth-first search) es un algoritmo que explora los nodos en un grafo, en orden inverso de la distancia de aumento desde el nodo inicial. Cálculo de la Ruta Más Corta Los cálculos de la ruta más corta son una familia de algoritmos que determinan la distancia más corta entre nodos de un grafo Existen diferentes algoritmos de ruta más corta, debido a que diferentes tipos de grafos requieren enfoques un poco diferentes En un grafo no ponderado, por ejemplo, se puede usar simplemente una búsqueda por niveles para calcular la distancia más corta entre nodos Para grafos ponderados, se deben utilizar algoritmos diferentes y un poco más complejos Podemos usar el algoritmo Dijkstra si todos los pesos o valores en un grafo ponderado son positivos. Un algoritmo conocido como Bellman-Ford resuelve el problema de la ruta más corta para grafos que contienen aristas con valores negativos

ALGORITMOS DE ORDENACIÓN BÁSICOS

Existen diferentes algoritmos de ordenación elementales

...