ayuda sobre grafos

Archivado
Hola gente, necesito ayuda haber si alguien me puede echar una mano, he buscado en el google pero no he sacado nada claro, tengo que hacer un programa que calcule las componentes conexas a partir de un grafo, si alguien tuviera un libro de algoritmia y me pusiera algun algoritmo o explicacion se lo agradeceria mucho.

Saludos
¿Ni siquiera conoces un algoritmo? Es muy sencillo, se basa en una búsqueda por anchura.

Utiliza dos estructuras: una lista con todos los vértices, donde inicialmente estén todos como no marcados, y una cola. Comienza por un vértice al azar, márcalo, y añade sus vértices adyacentes a la cola. A partir de ahí siempre se repite el mismo proceso: el primer vértice de la cola se saca de ella, se pone como marcado, y se añaden a la cola aquellos vértices adyacentes a él que aún no estén marcados y que no estuviesen ya en la cola. Cuando la cola se agote, habrás conseguido una componente conexa. Si quedan vértices sin marcar, empieza una nueva componente eligiendo otro vértice al azar, y vuelve a ejecutar el algoritmo. Así hasta que no queden vértices sin marcar.
ai un hombre sabio [tadoramo]
Maestro Yoda escribió:¿Ni siquiera conoces un algoritmo? Es muy sencillo, se basa en una búsqueda por anchura.

Utiliza dos estructuras: una lista con todos los vértices, donde inicialmente estén todos como no marcados, y una cola. Comienza por un vértice al azar, márcalo, y añade sus vértices adyacentes a la cola. A partir de ahí siempre se repite el mismo proceso: el primer vértice de la cola se saca de ella, se pone como marcado, y se añaden a la cola aquellos vértices adyacentes a él que aún no estén marcados y que no estuviesen ya en la cola. Cuando la cola se agote, habrás conseguido una componente conexa. Si quedan vértices sin marcar, empieza una nueva componente eligiendo otro vértice al azar, y vuelve a ejecutar el algoritmo. Así hasta que no queden vértices sin marcar.


gracias por la respuesta [oki]
tambien existe el algoritmo por profundidad DFS, pero tal como te ha explicado MY esta perfecto..

Este enero saque un 8,2 de grafos y casi ni me acuerdo ya [+risas]
kurras escribió:tambien existe el algoritmo por profundidad DFS, pero tal como te ha explicado MY esta perfecto..

Este enero saque un 8,2 de grafos y casi ni me acuerdo ya [+risas]

Así va el país [jaja] .
Maestro Yoda escribió:Así va el país [jaja] .

eso repasando se recuerda enseguida.. xD

Para que no os quejeis, aqui tienes el BFS en algoritmo, pasarlo a C o lo que sea no deberia ser muy complicado


Imagen
6 respuestas
Archivado
Volver a Miscelánea