Scribd
Cargar
119 vistas6 páginas

Algoritmo Bfs

El documento trata sobre el origen y definición de los grafos. Explica que la palabra "grafo" proviene del griego y significa "trazar". Un grafo se define como un conjunto de vértices unidos por aristas o arcos que representan relaciones binarias. Comúnmente los grafos se representan gráficamente mediante puntos y líneas. El algoritmo BFS se usa para recorrer grafos de manera no informada empezando por la raíz y explorando los vecinos de cada nodo de manera amplia.

Cargado por

Emiliano Rodríguez Rodríguez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
119 vistas6 páginas

Algoritmo Bfs

El documento trata sobre el origen y definición de los grafos. Explica que la palabra "grafo" proviene del griego y significa "trazar". Un grafo se define como un conjunto de vértices unidos por aristas o arcos que representan relaciones binarias. Comúnmente los grafos se representan gráficamente mediante puntos y líneas. El algoritmo BFS se usa para recorrer grafos de manera no informada empezando por la raíz y explorando los vecinos de cada nodo de manera amplia.

Cargado por

Emiliano Rodríguez Rodríguez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

• Grafos: Origen

• El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como
respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes: gráfico de una serie de
tareas a realizar indicando su secuenciación (un organigrama),grafos matemáticos que representan las relaciones
binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso,
es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con
líneas conectándolos (arcos).

• De aquí se podría deducir que 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.
GRAFO: DEFINICION

Es un conjunto de objetos llamados vértices o nodos unidos por


enlaces llamados aristas o arcos , que permiten
GRAFO CON 6 VERTICES Y 7
representar relaciones binarias entre elementos de un ​Son objeto ARISTAS
de estudio de la teoría de grafos

Típicamente, un grafo se representa gráficamente como un


conjunto de puntos (vértices o nodos) unidos por líneas (aristas o
arcos).

Desde un punto de vista práctico, los grafos permiten estudiar las


interrelaciones entre unidades que interactúan unas con otras.
ALGORITMO BFS

• Búsqueda en anchura (en ingles BFS - Breadth First Search) es un algoritmo de búsqueda


no informada utilizado para recorrer o buscar elementos en un grafo (usado frecuentemente
sobre arboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento
raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación
para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que
se recorra todo el árbol.
Problema propuesto
• En una empresa de viajes se les ofrece a unas familias que iba ciertos lugares un viaje en el
cual consistía ciertas paradas o ciertos destinos en el cual podían llegar a ese lugar y
quedarse dos días y una noche y después se irían a otro destino pero ellos llegarían a cierto
destino para quedarse en ese lugar mas tiempo, lo cual para esto veremos cuantos viajes o
cuantos destino hace cada familia y ver la distancia que hay entre cierto paradas que se
hacen. Y para esto ocuparemos el algoritmo BFS.
• Pseudocódigo

También podría gustarte