C Funcao que identifica se grafo de matriz de adjacencia e ciclico ou aciclico

Nelsonderocha · 24 de junho de 2022

preciso de uma funcao que determine se o grafo representado por matriz de adjacencia eh ciclico ou aciclico.

#include <stdio.h>
#include <stdlib.h>
#define branco 0
#define cinza 1
#define preto 2



typedef struct{
   int V;
   int A;
   int *cor;
   int **mat;
}GrafoMA;

Nelsonderocha · 25 de junho de 2022

20 horas atrás, Nelsonderocha disse:
preciso de uma funcao que determine se o grafo representado por matriz de adjacencia eh ciclico ou aciclico.
#include <stdio.h>
#include <stdlib.h>
#define branco 0
#define cinza 1
#define preto 2



typedef struct{
   int V;
   int A;
   int *cor;
   int **mat;
}GrafoMA;

o codigo que fiz ate agr

#include <stdio.h>
#include <stdlib.h>
#define branco 1
#define cinza 2
#define preto -1

typedef struct{
   int V;
   int A;
   int *cor;
   int **mat;
}GrafoMA;

int dfs(GrafoMA *g, int i, int p){
    int v;

    g->cor[i]=cinza;

    for(v=0;v<g->V;v++){
        if(g->mat[i][v]){
            if(v == p)
                continue;
            if(g->cor[v] == cinza)
                return 1;
            if(dfs(g,v,i)==1)
                return 1;
        }
    }
    return 0;
}

int ciclo(GrafoMA *g){
    int v;
    for(v=0;v<g->V;v++){
        if(g->cor[v]==cinza)
            continue;
        if(dfs(g,v,-1)==1){
            return 1;
        }
    }
    return 0;
}


int main(){
    int v, i,j,n;

    scanf("%d", &v);
    GrafoMA *g = iniciar_grafoMA(v);
    for(i=0;i<v;i++){
        for(j=0;j<v;j++){
            scanf("%d", &n);
            g->mat[i][j] = n;
        }
    }
    if(ciclo(g)==1){
        printf("ciclico");
    }
    else{
        printf("aciclico");
    }
    return 0;
}