Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Algoritmia » grafos dirigidos aciclicos

Algoritmia - grafos dirigidos aciclicos

Volver
Nuevo Tema
<<>>
 
Vista:

grafos dirigidos aciclicos

Publicado por jorge (1 intervención) el 26/03/2005 22:23:25
necesito que me yuden con los GDA necesito una idea para hacer grafos de estos en c++
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Creación de grafos dirigidos acíclicos (GDA) en C++

Publicado por Alejandro (307 intervenciones) el 05/03/2024 00:28:49
Jorge, para crear grafos dirigidos acíclicos (GDA) en C++, puedes utilizar una representación basada en listas de adyacencia y luego implementar algoritmos para garantizar la aciclicidad. Aquí hay un enfoque básico:

1. Representación del grafo:
Utiliza una estructura para representar el grafo. Puedes usar un `vector` de `listas` o `conjuntos` para almacenar las adyacencias.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <list>
 
using namespace std;
 
class GrafoDirigidoAciclico {
public:
    int V; // Número de vértices
    vector<list<int>> adyacencias; // Lista de adyacencias
 
    GrafoDirigidoAciclico(int vertices) : V(vertices), adyacencias(vertices) {}
 
    void agregarArista(int origen, int destino) {
        adyacencias[origen].push_back(destino);
    }
 
    // Implementa métodos adicionales según sea necesario
};
 
int main() {
    // Ejemplo de creación de un Grafo Dirigido Acíclico
    GrafoDirigidoAciclico gda(5);
 
    gda.agregarArista(0, 1);
    gda.agregarArista(0, 2);
    gda.agregarArista(1, 3);
    gda.agregarArista(2, 4);
 
    // Puedes agregar más aristas según tus necesidades
 
    return 0;
}

2. Verificación de aciclicidad:
Implementa un algoritmo como el de búsqueda topológica para verificar la existencia de ciclos en el grafo. Si el grafo no tiene ciclos, entonces es un grafo dirigido acíclico (GDA).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <vector>
#include <list>
#include <stack>
 
using namespace std;
 
class GrafoDirigidoAciclico {
    // ... (como se definió anteriormente)
 
public:
    bool tieneCiclos() {
        vector<int> visitado(V, 0); // 0: No visitado, 1: En proceso, 2: Visitado
        stack<int> pila;
 
        for (int i = 0; i < V; ++i) {
            if (visitado[i] == 0 && tieneCiclosUtil(i, visitado, pila)) {
                return true;
            }
        }
 
        return false;
    }
 
private:
    bool tieneCiclosUtil(int v, vector<int>& visitado, stack<int>& pila) {
        visitado[v] = 1; // En proceso
 
        for (int vecino : adyacencias[v]) {
            if (visitado[vecino] == 0 && tieneCiclosUtil(vecino, visitado, pila)) {
                return true;
            }
            else if (visitado[vecino] == 1) {
                return true; // Ciclo detectado
            }
        }
 
        visitado[v] = 2; // Visitado
        pila.push(v);
 
        return false;
    }
};

3. Uso del grafo:
Utiliza los métodos proporcionados por la clase `GrafoDirigidoAciclico` para trabajar con tu grafo dirigido acíclico.

Este es un punto de partida básico, y puedes ampliar y ajustar según tus necesidades específicas.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar