Detecção de ciclos em um grafo
//mostrar os ciclos existentes em um grafo
#include
#include
int vi;
struct aresta{ int destino; float custo; struct aresta *prox;
};
struct vertice{ int origem; struct aresta *arestas; struct vertice *prox;
}*grafo = NULL;
struct pilha{ int vertice; struct pilha *prox;
}*caminho = NULL;
struct ciclo{ struct pilha *vertices; struct ciclo *prox;
}*ciclos = NULL;
void inicializar_aresta(struct aresta *&a){ struct aresta *t; while (a != NULL){ t = a; a = a->prox; delete(t); }
}
void inicializar_vertice(struct vertice *&g){ struct vertice *t; while (g != NULL){ t = g; g = g->prox; inicializar_aresta(t->arestas); delete(t); }
}
void inicializar_pilha(struct pilha *&l){ struct pilha *p; while (l != NULL){ p = l; l = l->prox; delete(p); }
}
void inicializar_ciclo(struct ciclo *&l){ struct ciclo *p; while (l != NULL){ p = l; l = l->prox; delete(p); }
}
void empilha(struct pilha *&l, int i){ struct pilha *p, *n; n = new(struct pilha); n->vertice = i; n->prox = NULL; if (l != NULL){ for (p = l; (p->prox != NULL); p = p->prox); p->prox = n; } else{ l = n; }
}
int desempilha(struct pilha *&l){ struct pilha *a, *p; int vertice;
if(l != NULL){ for (a = NULL, p = l; (p->prox != NULL); a = p, p = p->prox); vertice = p->vertice; if(a != NULL) a->prox = NULL; else l = NULL; delete(p); return vertice; } return 0;
}
int estah_na_pilha(struct pilha *l, int valor){ struct pilha *p; for(p = l; p != NULL; p = p->prox){ if(p->vertice == valor){ return 1; } } return 0;
}
struct vertice * procurar_vertice(struct vertice *g, int v){ struct vertice *p; for(p = g; p != NULL; p = p->prox){ if(p->origem == v) return p; } return NULL;
}
struct aresta * procurar_aresta(struct vertice