Tarea3 Detección de Ciclos

Detección de ciclos en BFS

Un BFS (Breadth First Search) Es un algoritmo para recorrer o buscar elementos en un grafo, esta se empieza de la raíz y se exploran todos los vecinos de este nodo. Y luego para cada uno de los vecino se explora sus respectivos vecinos, y así hasta que se recorra todo el grafo o árbol.

Procesamiento

Dado un vértice fuente s, Breadth-first search sistemáticamente explora los vértices de G para “descubrir” todos los vértices alcanzables desde s.

Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables

Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables.

El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices.

Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1.

Aplicaciones

Las aplicaciones que se pueden usar para este algoritmo son:

• Como la solución de circuitos eléctricos
• Exploración en entornos de robótica móvil
• Control de información en redes informáticas, entre otras...

Detección de Ciclos

Como su nombre lo indica, la detección de ciclos, sirve para detectar ciclos en el BFS, el algoritmo mas visto sobre esto es el algoritmo de la liebre y la tortuga.

Lo que hace este algoritmo es de que:

Tanto como la tortuga y la liebre son punteros, y ambos empiezan en el inicio del grafo. Para cada iteración o bien , para cada paso la tortuga avanzara un paso, y la liebre avanzara dos pasos. Si es que existe un ciclo, la liebre ira por ese ciclo y es posible que mas de una ves, y en algún tiempo la liebre se encontrara con nuestra tortuga. Si esto sucede, quiere decir que existe un ciclo. En caso de que no exista ningún ciclo, tanto como la tortuga y la liebre llegaran al final del grafo, sin tener que toparse.

Aquí les dejo un código en c de Detección de Ciclos en el cual me lo encontré en http://en.literateprograms.org/Floyd's_cycle-finding_algorithm_(C)

Deteccion de Ciclos

View more documents from Abraham.

Aquí si lo quieren descargar.

En esta parte esta el codigo que implemente:

Deteccion de Ciclos en c

View more documents from Abraham.

Aqui si se quiere descargar

Y necesita un archivo .txt, ya que te pide que des el nombre del archivo, descargas este, mas adelante esta una imagen de como son los grafos.