Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmo de Warshall

No description
by

Lady Perilla

on 5 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo de Warshall

-Algoritmo de Warshall
-Recorrido a lo Ancho de un Grafo
-Recorrido en Profundidad Omar Moreno
Lady Perilla Algoritmo de Warshall El objetivo de este algoritmo es mejorar el método descrito anteriormente de matriz de caminos. Se mostrará el funcionamiento de este método mediante el ejemplo del siguiente dígrafo: Se puede observar que la fila#3 ha sido transformada como imagen de la fila#1 solo en aquellos casos donde la fila#1 tiene 1y la fila#3 tenía 0.
Siguiendo este recorrido por la columna 1, entre 5:1, 6:1, 7:1 y 8:1, no existe camino. Entre 9:1 si existe camino, lo cual indica que entre 9 y todos los vértices que tengan como parte del camino el vértice 1, existirá camino. Entre 9:2 y 9:4 existe, por lo tanto un camino. Esto nos obliga a transformar la matriz así:
Formas de Recorrer un Grafo Un grafo a lo ancho se recorre por niveles. Para explicar como se realiza
este recorrido se tomará el siguiente ejemplo: Para este algoritmo, siempre se comienza con el vértice 1, y se desplazan por la columna 1, preguntando si existe camino entre 1:1, 2:1 y 3:1. Como entre 3:1 si existe camino, evidentemente existirá camino entre 3 y todos los vértices que tengan camino a partir del vértice 1. Esta última conclusión nos permite afirmar que entre 3 y 2 existe camino y entre 3 y 4 existe camino, lo que obliga a transformar la matriz original así: Se continúa analizando el vértice No. 2, es decir, la columna#2. En este caso se trabaja con las filas 3 y 9 ya que son los vértices que tienen camino con el vértice 2. Al decir que se transforma, significa proyectar los unos (1´s) de la fila analizada (fila#2) sobre las filas que tienen camino (fila#1, fila#3 y fila#9).
Ahora obsérvese como va quedando la matriz después de haber analizado el vértice#2:
Recorrido a lo Ancho de un Grafo Supóngase que el grafo se encuentra almacenado en una lista de adyacencia. El recorrido a lo ancho nos debe informar los siguientes datos
•El orden de visita a cada vértice
•El padre de cada vértice
Por ejemplo, si el vértice 2 se visitó de tercero, cuarto o sexto, etc. EL significado de “padre de cada vértice” corresponde al vértice padre del vértice que se está visitando. Por ejemplo, si el recorrido a lo ancho es: 1, 3, 2, 8, 5, 7, 6, 4.
La función debe informar que el padre del vértice 8 es el vértice 3 ó el padre del vértice 4 es el vértice 8. El padre del vértice con el cual comienza el recorrido es siempre 0.
La lista de adyacencia recorriendo este grafo, partiendo del vértice 1, queda de la siguiente manera: El recorrido resultado a lo ancho del grafo es: 1, 3, 2, 8, 5, 7, 6, 4.
Utilizando la variable padre de la lista de adyacencia, se puede graficar el árbol expandido del grafo:
Recorrido en Profundidad El recorrido en profundidad de un grafo se asemeja al recorrido inorden de un árbol. Para explicar este recorrido, se tomará el siguiente grafo como ejemplo:






De la misma manera que al recorrer el grafo a lo ancho, el árbol expandido es diferente dependiendo del vértice por el cual se comience el recorrido. Se ilustrará el método comenzando desde el vértice 7 y considerando que la lista de adyacencia está construida así:
El método para recorrer un grafo en profundidad, consiste en visitar el vértice original (7), luego el primer adjunto a ese vértice (3), luego el primer adjunto de este vértice (2), luego el primer adjunto de este vértice (1), y así sucesivamente. Siguiendo este método recursivo, el recorrido del grafo anterior es: 7, 3, 2, 1, 4, 5, 6, 8, 9.
De esta forma, queda como lista de adyacencia y árbol expandido los siguientes:
A continuación se mostrarán las diferencias que presentan la lista de adyacencia y el árbol expandido, recorriendo el mismo grafo en profundidad, pero comenzando desde el vértice 2:
Full transcript