programacion de grafos

[verakra]

soy un poco nuevo en programacion y deseo saber como se puede hacer el ejemplo

[NextByte]

Buenas , no soy un experto en el área pero personalmente en este tipo de algoritmos me ayuda mucho el realizar una prueba de escritorio o pensar el algoritmo antes de irme al código. Para dar inicio al problema es importante saber que es lo que se intenta realizar con este algoritmo. El algortimo de bfs esta hecho para hacer un recorrido a partir de un nodo inicial por cada uno de los nodos de un grafo de manera que cuando llegamos a cada uno de estos nodo nosotros podemos procesarlo , en este caso escribirlo en pantalla.El recorrido de anchura también es conocido como recorrido por niveles , este es un punto importante para entenderlo. Yo lo consideraría como una jerarquía en una empresa. Tenemos 1 jefe, 4 subjefes y finalmente 5 empleados. El objetivo es llegar con cada personal empezando por el jefe, primero vamos a visitar al jefe, después a un subjefe, después al 2do subjefe, después al 3ro..... y asi sucesivamente hasta terminar con los subjetefes, una vez terminada la visita de los subjefes seguiría la visita de cada uno de los empleados.
Ojo. El algortimo va determinar el orden que en el que se van a visitar los miembros de cada subnivel , lo importante es entender que primero visitamos a todos los nodos(personas) del mismo nivel , una vez que terminamos con un nivel nos vamos a visitar a los del siguiente nivel y asi sucesivamente...

Ahora aterrizando esta idea en la teoría de grafos.... Tenemos un grafo como el que nos presentas en el cual queremos partir de un nodo para hacer un recorrido por amplitud. Lo primero es ver cual es el nivel mas "cercano" a este grafo, en otras palabras, ¿Que nodos son adyacentes al inicial?, Va... En este momento debemos considerar que no queremos procesar dos veces a un mismo nodo por lo cual podriamos llevar un control(un arreglo) que nos permita saber que nodos ya han sido visitados.

Pasos.
1. Empezamos en el nodo 1.
2. La bandera que corresponde al visitado del nodo 1 se activa.
3. Metemos al nodo 1 en una cola.
4. Empieza un ciclo que continuara mientras la cola no este vacía.
    5. Sacas un nodo de la cola.
    6. Lo procesas(Escribes en pantalla)
    7. Metes todos sus adyacentes a este nodo asegurandote que ninguno de ellos hayan sido visitados anteriormente. (OJO. Cuando agregas algún nodo adyacente debes activar su correspondiente bandera que permita saber que ya fue visitado, es decir, que ya fue ingresado en algun momento a la cola).
8.Fin_Ciclo de paso 4

De esta manera la cola nos va determinar la secuencia con la que vamos a procesar cada nodo y si nos ponemos a pensar esto no es tan dificil de ver, al fin de cuenta lo que estamos haciendo es meter los elementos en la cola por niveles de adyacencia. Primero metemos los nodos que se encuentran en el primer nivel de adyacencia, despues metemos los nodos con el siguiente nivel de adyacencia y asi sucesivamente de manera que la cola nos va ir generando la salida de manera que el primero que entro va ser el primero que va salir , es decir, el primer nivel de nodos que entro va ser el primer nivel de nodos que va ser procesado.

Una vez analizando un poco el algoritmo ya puedes considerar hacer una primera implementación del código en algún lenguaje de programación, tu siguiente paso es programarlo y ver que parte aún causa problemas.

[CalgaryCorpus]

Sugiero una correccion a la explicacion anterior: donde dice 'pila' cambiar por 'cola'

[NextByte]

Sugiero una correccion a la explicacion anterior: donde dice 'pila' cambiar por 'cola'

Listo. Una disculpa por el descuido.

[verakra]

Como les digo no soy un experto en programación, deseo saber como se aria utilizando C++,, como es el codigo final, porque la explicacion ya me la dieron, pero como estoy apenas empezando a programar, no se ni como empezarlo

[srWhiteSkull]

Muestra como haces los grafos (el código).

[verakra]

como les vengo no diciendo, no se ni como empezar a programar grafos , pero quiero aprender, por eso busque , y encontre ese ejemplo y quiero saber como programarlo

[NextByte]

Creo que para comenzar debes pensar en como representar un grafo dentro de tu programa. Debido a que este programa no necesita el peso de los vértices de un grafo te puede bastar con algo llamado matriz de adyacencia u otra forma seria una lista de adyacencia que es algo cercano a la matriz de adyacencia pero sin embargo solo almacena valores para los nodos con adyacencia... Personalmente creo que la matriz de adyacencia es la más facil tanto de implementar como de entender.

En resumen la matriz de adyacencia es una matriz cuadrada de longitud igual al numero de nodos en donde  cada uno de sus valores puede tener solo dos valores(booleano) , un valor true determina que existe adyacencia mientras que un valor false determina que no existe adyacencia, es decir, no existe conexión entre esos dos vertices.

Ejemplo de matriz de adyacencia de la imagen:

0	1	1	0	0	0
1	0	0	1	1	0
1	0	0	0	1	0
0	1	0	0	1	1
0	1	1	1	0	1
0	0	0	1	1	0

En pocas palabras la primera fila representa las conexiones o adyacencias con otros vértices a partir del vértice '1' o del primer vértice, la segunda fila representa las conexiones con otros vértices a partir del vértice '2' o del segundo vértice y así sucesivamente.
Nota. La matriz de adyacente tiene ambigüedades pensando en que se trata de un grafo no dirigido por lo cual es redundante representar la conexión de A->B y B->A .


En resumen la anterior matriz de adyacencia representa:

1. El vertice 1 tiene adyacencia con el vertice 2 y 3.
2. El vertice 2 tiene adyacencia con el vertice 1,4 y 5.
3. El vertice 3 tiene adyacencia con el vertice 1 y 5.
4. El vertice 4 tiene adyacencia con el vertice 2,5 y 6.
5. El vertice 5 tiene adyacencia con el vertice 2,3,4 y 6.
6. El vértice 6 tiene adyacencia con el vértice 4 y 5.

Es importante tomar en cuenta que en C++ los arreglos comienzan en el indice 0 por lo cual podríamos decir que la fila n representa la adyacencia  del vértice n+1.
Ejemplo
Matriz_Adyacencia[ 0 ][ . . . ] representa un valor de adyacencia del vértice 1 ( 0 +1 )

A partir de lo anterior ya podrías empezar a aplicar el algoritmo debido a que ya tienes la representación del grafo, en el problema se plantea el uso de una cola la cual no es necesario que revises a detalle su implementación debido a que ya existe una clase definida en C++ la cual puedes utilizar aunque personalmente yo recomendaría ver ese tipo de temas antes de llegar al tema de grafos.

   

[CalgaryCorpus]

Sugiero que busques "BFS C++" en google, seguro que encontraras codigos para empezar ahi.

[srWhiteSkull]

como les vengo no diciendo, no se ni como empezar a programar grafos , pero quiero aprender, por eso busque , y encontre ese ejemplo y quiero saber como programarlo

Si de verdad quieres "aprender" entonces deberías olvidarte de los grafos, de momento, y aprender otras cosas básicas como por ejemplo las listas enlazadas. Tú problema es que arrastras un déficit de conocimientos en la programación básicos y es difícil comprender, en caso de que estuvieras cursando programación, cómo has llegado hasta los grafos