Tarea # 3

Que tal compañeros esta vez vengo a hablar de la búsqueda por anchura esta a diferencia de la búsqueda por profundidad es que esta usa una cola en vez de una pila.

acá dejare la liga para la descarga del archivo ó podrán verlo mas abajo si tiene instalado el plug-in de adobe flash.

código para descarga.
archivo .dat que contiene los nodos descarga.
Definición
¿Que es el BFS? es un algoritmo de búsqueda por anchura que dado un nodo inicial viaja por los vértices hacia los vecinos de este, después viaja através de los vértices de sus vecinos y así sucesivamente hasta visitar cada nodo del grafo.

¿Que es el coloreo de grafos? se dice que es un caso etiquetado de grafos en el cual asignamos
unas etiquetas llamadas colores, bien pues el objetivo de esto es colorear un nodo de tal manera que se use la menor cantidad de colores posibles cumpliendo con la condición de que no debe tener el mismo color dos nodos que estén unidos entre si.
Objetivo
Bien pues a mi me toco utilizar dicho algoritmo para la coloración de un grafo con dos colores, de esta manera al aplicar el algoritmo si detectaba un ciclo no seria posible que fuese dos coloreable.

Procedimiento
Bien pues el procedimiento para resolver este problema lo realice de una manera utilizando un código que ya antes teníamos este código fue uno realizado en clase en el cual simulaba las acciones de un algoritmo de DFS, bien pues apartir de este tomando la parte del código donde
abrimos un archivo creado por nosotros donde almacenamos:

• El numero de nodos
• El numero de aristas
• Las uniones de los nodos
• El peso de las aristas

Al leer estos datos del archivo pasamos a implementarlos al BFS de tal manera que nuestro primer nodo tomaría el primer color y almacenándolo dentro de una cola después de esto pasamos a visitar a uno de los vecinos (en este caso elegí que se escogiera la arista de menor peso).

Al pasar a los vecinos a cada uno de ellos se le asignaba un color dos, y así sucesivamente a sus vecinos de nuevo el color uno y cada uno de los nodos no visitados se agregaba dentro de la cola
de manera que al final nos imprimiría el orden del recorrido (solo imprimiendo visitados) y con su respectivo color.

Si llegase a ser que mas de un nodo comparte una arista con otro del mismo color llegamos a la conclusión de que no es dos-coloreable.

Observaciones
Bueno una de las observaciones es que este código puede implementarse dentro de una detección de ciclos pues en el caso de que nuestro grafo no sea dos-coloreable indica que existe un ciclo dentro de nuestro grafo y así como para este caso sirve el decir que no es dos coloreable para una detección de ciclos diría que si existe tal.

Coloreo de grafos

View more documents from Jorge.