programacion de grafos

Iniciado por verakra, 21 Marzo 2019, 04:45 AM

0 Miembros y 1 Visitante están viendo este tema.

verakra

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




NextByte

#1
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'
Aqui mi perfil en LinkedIn, invitame un cafe aqui

NextByte

Cita de: CalgaryCorpus en 21 Marzo 2019, 13:40 PM
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

#7
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:

011000
100110
100010
010011
011101
000110

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.
Aqui mi perfil en LinkedIn, invitame un cafe aqui

srWhiteSkull

Cita de: verakra en 23 Marzo 2019, 05:00 AM
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  :¬¬