Witam
Mam posortować topologicznie graf z reprezentacji macierzy grafu metodą usuwania wierzchołków o stopniu wejściowym 0 (DEL). Napisałem funkcje tworzącą macierz grafu z macierzy sąsiedztwa i teraz nie mogę wykombinować jak to sortować. Bardzo proszę o wskazówki jak do tego podejść. Nie proszę o kod tylko o wskazówki jak ma wyglądac ten algorytm sortowania. Z góry dziękuję
Oto kod tworzenia macierzy grafu:
void tworzenie_mgrafu(int x, int y) //x - liczba wierzchołków, y - liczba krawędzi
{
//Alokowanie pamięci dla macierzy sąsiedzctwa - MS[][] i tablicy stopni wejściowych - indeg[]
int MS[x + 1][x + 1];
int indeg[x + 1];
//Zerujemy tablicę list sąsiedztwa i tablicę stopni wejściowych
for(int i = 1; i <= x; i++)
{
for (int j = 1; j <= x; j++) MS[i][j]=0;
indeg[i] = 0;
}
//Wczytywanie i umieszacznie w macierzy sąsiedzctwa krawędzi grafu i uzupełnianie tablicy stopni wejściowych
for(int i = 1; i <= y; i++)
{
int u,v;
cin >> u >> v;
MS[u][v]=1;
indeg[v]++;
}
//Alokowanie pamięci dla tablic list następników - LN[], poprzedników - LP[] i krawędzi nieincydentnych - LNI[]
el_listy * LN[x + 1];
el_listy * LP[x + 1];
el_listy * LNI[x + 1];
el_listy * p;
//Zerujemy tablice list
for(int i = 1; i <= x; i++)
{
LP[i] = NULL;
LN[i] = NULL;
LNI[i] = NULL;
}
//Uzupełnianie LN LP i LNI z macierzy grafu
for (int i = 1; i <= x; i++)
{
for (int j = 1; j <= x; j++)
{
//Tworzenie następników i poprzedników
if (MS[i][j]==1)
{
//Tworzenie list następników
el_listy * tym = new el_listy;
tym->next=NULL;
tym->u=j;
if (LN[i]==NULL)
{
LN[i]=tym;
}
else
{
p=LN[i];
while(p->next!=NULL) p=p->next;
p->next=tym;
}
//Tworzenie list poprzedników
el_listy * tym2 = new el_listy;
tym2->next=NULL;
tym2->u=i;
if (LP[j]==NULL)
{
LP[j]=tym2;
}
else
{
p=LP[j];
while(p->next!=NULL) p=p->next;
p->next=tym2;
}
}
//Tworzenie list krawędzi nieincydentnych
else if ((MS[i][j]==0) && (MS[j][i]==0))
{
el_listy * tym3 = new el_listy;
tym3->next=NULL;
tym3->u=j;
if (LNI[i]==NULL)
{
LNI[i]=tym3;
}
else
{
p=LNI[i];
while(p->next!=NULL) p=p->next;
p->next=tym3;
}
}
}
}
//Alokowanie pamięci dla macierzy grafu - MG[][]
int MG[x + 2][x + 2];
for (int i=0; i<x+2; i++)
{
for (int j=0; j<x+2; j++) MG[i][j]=0;
}
//Uzupełnianie macierzy grafu
for (int i=1; i<=x; i++)
{
//Uzupełnianie następników
if (LN[i]==NULL)
{
MG[i][x+1]=0;
MG[x+1][i]=0;
}
else
{
p=LN[i];
MG[i][x+1]=p->u;
while (p->next!=NULL)
{
MG[i][p->u]=p->next->u+x;
p=p->next;
}
MG[i][p->u]=p->u+x;
MG[x+1][i]=p->u;
}
//Uzupełnianie poprzedników
if (LP[i]==NULL)
{
MG[i][0]=0;
MG[0][i]=0;
}
else
{
p=LP[i];
MG[i][0]=p->u;
while (p->next!=NULL)
{
MG[i][p->u]=p->next->u;
p=p->next;
}
MG[i][p->u]=p->u;
MG[0][i]=p->u;
}
//Uzupełnianie nieincydentnych
if (LNI[i]!=NULL)
{
p=LNI[i];
while (p->next!=NULL)
{
MG[i][p->u]=-(p->next->u);
p=p->next;
}
MG[i][p->u]=-(p->u);
}
}
//Wypisywanie macierzy grafu
for (int i=0; i<x+2; i++)
{
for (int j=0; j<x+2; j++) cout << MG[i][j] << " ";
cout << endl;
}
}