Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » C/Visual C » Ayuda en grafos en C++

C/Visual C - Ayuda en grafos en C++

Volver
Nuevo Tema
<<>>
 
Vista:

Ayuda en grafos en C++

Publicado por Robert Mejia (1 intervención) el 20/09/2000 00:00:00
Necesitamos alguien que nos pueda proporcionar el codigo o una nocion de este para los siguientes problemas:

1.Escriba un programa para determinar si un grafo dirigido aciclico GDA posee raiz.

2.Escriba un programa para encontrar el camino mas largo en un GDA

3.Escriba un programa que tome como entrada un grafo dirigido y 2 de sus vertices.El programa debe imprimir todos los caminos simples que vayan de un vertice a otro.

4.Escriba un programa para encontrar todos los componentes conexos de un grafo.

5.Escribase un programa de orden O(n) para determinar si un grafo de N vertices contiene un ciclo.

6.Escribase un programa para enumerar todos los ciclos simples de un grafo.

Si alguien tiene piedad de mi porfavor mandeme lo que sea a mi e-mail , gracias de antemano
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

Soluciones para problemas en grafos dirigidos acíclicos (GDA)

Publicado por Alejandro (913 intervenciones) el 03/09/2024 17:01:30
1. Programa para determinar si un GDA posee raíz:
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
43
44
45
46
47
48
#include <stdio.h>
 
int tieneRaiz(int grafo[][100], int n) {
    int i, j;
    int tienePredecesor[n];
 
    // Inicializar el arreglo de predecesores
    for (i = 0; i < n; i++) {
        tienePredecesor[i] = 0;
    }
 
    // Verificar si cada vértice tiene predecesor
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (grafo[j][i] == 1) {
                tienePredecesor[i] = 1;
                break;
            }
        }
    }
 
    // Verificar si hay algún vértice sin predecesor
    for (i = 0; i < n; i++) {
        if (tienePredecesor[i] == 0) {
            return 1; // El grafo tiene raíz
        }
    }
 
    return 0; // El grafo no tiene raíz
}
 
int main() {
    int grafo[100][100] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    int n = 4;
 
    if (tieneRaiz(grafo, n)) {
        printf("El grafo tiene raiz.\n");
    } else {
        printf("El grafo no tiene raiz.\n");
    }
 
    return 0;
}

2. Programa para encontrar el camino más largo en un 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
#include <stdio.h>
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
int caminoMasLargo(int grafo[][100], int n, int v, int visitado[]) {
    int i, maxDistancia = 0;
 
    visitado[v] = 1;
 
    for (i = 0; i < n; i++) {
        if (grafo[v][i] == 1 && !visitado[i]) {
            maxDistancia = max(maxDistancia, 1 + caminoMasLargo(grafo, n, i, visitado));
        }
    }
 
    visitado[v] = 0;
 
    return maxDistancia;
}
 
int main() {
    int grafo[100][100] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    int n = 4;
    int visitado[100] = {0};
    int i, maximo = 0;
 
    for (i = 0; i < n; i++) {
        maximo = max(maximo, caminoMasLargo(grafo, n, i, visitado));
    }
 
    printf("El camino más largo en el grafo es: %d\n", maximo);
 
    return 0;
}

3. Programa para imprimir todos los caminos simples entre dos vértices en un 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
43
#include <stdio.h>
 
void imprimirCaminos(int grafo[][100], int n, int v, int destino, int visitado[], int camino[], int pos) {
    int i;
 
    visitado[v] = 1;
    camino[pos] = v;
    pos++;
 
    if (v == destino) {
        for (i = 0; i < pos; i++) {
            printf("%d ", camino[i]);
        }
        printf("\n");
    } else {
        for (i = 0; i < n; i++) {
            if (grafo[v][i] == 1 && !visitado[i]) {
                imprimirCaminos(grafo, n, i, destino, visitado, camino, pos);
            }
        }
    }
 
    pos--;
    visitado[v] = 0;
}
 
int main() {
    int grafo[100][100] = {
        {0, 1, 1, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    int n = 4;
    int visitado[100] = {0};
    int camino[100];
    int origen = 0;
    int destino = 3;
 
    imprimirCaminos(grafo, n, origen, destino, visitado, camino, 0);
 
    return 0;
}

4. Programa para encontrar todos los componentes conexos de un grafo:
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
#include <stdio.h>
 
void DFS(int grafo[][100], int n, int v, int visitado[]) {
    int i;
 
    visitado[v] = 1;
    printf("%d ", v);
 
    for (i = 0; i < n; i++) {
        if (grafo[v][i] == 1 && !visitado[i]) {
            DFS(grafo, n, i, visitado);
        }
    }
}
 
void componentesConexos(int grafo[][100], int n) {
    int visitado[100] = {0};
    int i;
 
    for (i = 0; i < n; i++) {
        if (!visitado[i]) {
            printf("Componente conexo: ");
            DFS(grafo, n, i, visitado);
            printf("\n");
        }
    }
}
 
int main() {
    int grafo[100][100] = {
        {0, 1, 0, 0},
        {1, 0, 0, 0},
        {0, 0, 0, 1},
        {0, 0, 1, 0}
    };
    int n = 4;
 
    componentesConexos(grafo, n);
 
    return 0;
}

5. Programa para determinar si un grafo de N vértices contiene un ciclo en orden O(n):
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 <stdio.h>
 
int tieneCiclo(int grafo[][100], int n) {
    int i, j;
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (grafo[i][j] == 1 && grafo[j][i] == 1) {
                return 1; // El grafo contiene un ciclo
            }
        }
    }
 
    return 0; // El grafo no contiene un ciclo
}
 
int main() {
    int grafo[100][100] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 1, 0}
    };
    int n = 4;
 
    if (tieneCiclo(grafo, n)) {
        printf("El grafo contiene un ciclo.\n");
    } else {
        printf("El grafo no contiene un ciclo.\n");
    }
 
    return 0;
}

6. Programa para enumerar todos los ciclos simples de un grafo:
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
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
 
void DFS(int grafo[][100], int n, int v, int visitado[], int camino[], int pos) {
    int i;
 
    visitado[v] = 1;
    camino[pos] = v;
    pos++;
 
    if (pos > 2) {
        if (grafo[v][camino[0]] == 1) {
            printf("Ciclo: ");
            for (i = 0; i < pos; i++) {
                printf("%d ", camino[i]);
            }
            printf("\n");
        }
    }
 
    for (i = 0; i < n; i++) {
        if (grafo[v][i] == 1 && !visitado[i]) {
            DFS(grafo, n, i, visitado, camino, pos);
        }
    }
 
    pos--;
    visitado[v] = 0;
}
 
void ciclosSimples(int grafo[][100], int n) {
    int visitado[100] = {0};
    int camino[100];
    int i;
 
    for (i = 0; i < n; i++) {
        DFS(grafo, n, i, visitado, camino, 0);
    }
}
 
int main() {
    int grafo[100][100] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {1, 0, 0, 0}
    };
    int n = 4;
 
    ciclosSimples(grafo, n);
 
    return 0;
}

Espero que estas soluciones te sean útiles.
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