MatematicasDiscretas

5.3  ALGORITMOS DE RECORRIDO Y BÚSQUEDA Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodos de salida.existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad. Así, para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado.hay dos formas. Recorrido en profundidad (DFS) Recorrido en anchura (BFS) Algoritmo BFS El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial. Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también un vector de cola auxiliar para gestionar los vértices no visitados. En muchos casos es necesario ejecutar es...

5.2.1 MATEMÁTICAS Por medio de la teoría de los grafos podemos resolver diversos problemas, como la síntesis para circuitos secuenciales, contadores, o sistemas de apertura. Se utiliza en diferentes áreas por ejemplo, en las áreas de Sistemas y Computación, en áreas de ingeniería. También por medio de ellas podemos responder preguntas tales como, ¿Qué tarea debo hacer primero?, ¿Qué tiempo es más corto?, ¿Cuál es el más barato?, y así podemos obtener caminos óptimos para las soluciones aplicando diversos algoritmos como puede ser el algoritmo de Floyd.   Un grafo  G  es un par  (V,E)  donde: o     V ={v 1 ,…,v n }  es un conjunto de vértices o     E = {e 1 ,…,e m }  es un conjunto de aristas, o     Con cada  e k   Î  {v i , v j } , con   v i , v j  Î  V ,  v i  ≠ v j ·           Los vértice...