Skip to content

Instantly share code, notes, and snippets.

@diogofurtado
Last active July 2, 2022 00:03
Show Gist options
  • Save diogofurtado/707cfd0260a83671b332b8b52ce99485 to your computer and use it in GitHub Desktop.
Save diogofurtado/707cfd0260a83671b332b8b52ce99485 to your computer and use it in GitHub Desktop.
Ordenação Topológica
#include <stdio.h>
#define MAX_TASKS 39
//Cada vértice é uma variavel do tipo struct Predecessoras para poder expressar 1 ou 2 valores de vértices predecessores, (2 é o MÁXIMO de vértices
//predecessores de acordo com o nosso problema do Projeto,por isso usamos um vetor dessa struct ao invés de int)
typedef struct
{
int Pred1;
int Pred2;
}Predecessoras;
void preenche_vetor(Predecessoras *vet, int tam);
int verificaPred(Predecessoras *vet, int tam, int i);
int main()
{
int i;
Predecessoras vet[MAX_TASKS];
preenche_vetor(vet, MAX_TASKS);
for (i = 1; i <= MAX_TASKS; i++) // inicializa a função verificaPred para cada um dos 39 vértices
{
if ((vet[i - 1].Pred1 + vet[i - 1].Pred2) == 0) // Caso seja um vértice sem predecessores como os vértices 1, 10, 19 e 31
{
printf("%d\n", i);
}
else
{
verificaPred(vet, MAX_TASKS, i); //Chama a função verificaPred para um vértice COM predecessores
}
}
return 0;
}
int verificaPred(Predecessoras *vet, int tam, int i)
{
if ((vet[i - 1].Pred1 + vet[i - 1].Pred2) == 0)
{
return 0;
}
if (vet[i - 1].Pred1 != 0)
{
vet[i - 1].Pred1 = verificaPred(vet, tam, vet[i - 1].Pred1); // Chama função verificaPred para o primeiro Predecessor de Vet[i]
}
if (vet[i - 1].Pred2 != 0)
{
vet[i - 1].Pred2 = verificaPred(vet, tam, vet[i - 1].Pred2); // Chama função verificaPred para o segundo Predecessor de Vet[i]
}
if ((vet[i - 1].Pred1 + vet[i - 1].Pred2) == 0)
{
printf("%d\n", i);
return 0;
}
}
void preenche_vetor(Predecessoras *vet, int tam)
{
int i;
for (i = 1; i <= tam; i++)
{
switch (i)
{
case 1:
vet[i - 1].Pred1 = 0;
vet[i - 1].Pred2 = 0;
break;
case 5:
vet[i - 1].Pred1 = 3;
vet[i - 1].Pred2 = 0;
break;
case 10:
vet[i - 1].Pred1 = 0;
vet[i - 1].Pred2 = 0;
break;
case 11:
vet[i - 1].Pred1 = 7;
vet[i - 1].Pred2 = 0;
break;
case 13:
vet[i - 1].Pred1 = 9;
vet[i - 1].Pred2 = 12;
break;
case 19:
vet[i - 1].Pred1 = 0;
vet[i - 1].Pred2 = 0;
break;
case 20:
vet[i - 1].Pred1 = 14;
vet[i - 1].Pred2 = 0;
break;
case 28:
vet[i - 1].Pred1 = 23;
vet[i - 1].Pred2 = 0;
break;
case 30:
vet[i - 1].Pred1 = 28;
vet[i - 1].Pred2 = 0;
break;
case 31:
vet[i - 1].Pred1 = 0;
vet[i - 1].Pred2 = 0;
break;
default:
vet[i - 1].Pred1 = i - 2;
vet[i - 1].Pred2 = 0;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment