jueves, 8 de julio de 2010

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:


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.

2 comentarios:

  1. Bibliografia:
    http://htinajero.blogspot.com/2010/05/proyecto-numero-5.html#comments
    http://en.literateprograms.org/Floyd's_cycle-finding_algorithm_(C)
    http://jorgemtz90.blogspot.com/2010/05/proyecto-5.html

    ResponderEliminar