„Programozás/Algoritmusok” változatai közötti eltérés
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
→Topologikus rendezést megadó algoritmus: forráskód és tétel hozzáadása |
||
856. sor:
# amikor egy pont vizsgálatát befejezzük, akkor egy lánc elejére beszúrjuk
# A rendezés a lánc szerint Megj.: a pontok csökk. F érték szerint vannak
Ha a G irányított gráf körmentes, akkor pontjainak minden olyan <v1,...vn> felsorolása, amelyre
'''f (vi ) > f (vi+1 ); i = 1,...n − 1'''
G egy topologikus rendezése lesz bármely mélységi bejárással kiszámított f elhagyási függvényre.
:'''Java kód'''
<pre>
public class TopRend
{
private:
enum Paletta {Feher, Szurke, Fekete}; //Osztályra scope-ban érvényes változók
static Paletta[] Szin;
int[] R;
int n;
boolean MelyBejar(Graf G, int p)
{
Szin[p]=Paletta.Szurke; //p pontot szürkével jelöli
for (int q:G.Ki(p)) //p->q él vizsgálatának kezdete
{
if (Szin[q]==Paletta.Szurke) //kört találtunk, nem lehet rendezést csinálni hiba!
return false;
if (Szin[q]==Paletta.Feher)
{
if (!MelyBejar(G,q)) //Rekurzív hivás p pont q fiára
return false; //hiba hogyha találunk kört a leszármazottakban
}
}
R[n--]=p; //beirjuk a pontott az R lánc elejére. n-et a Rendez() a
Szin[p]=Paletta.Fekete; //G pontjainak számával teszi egyenlővé.
return true; //feketével jelöljük a sikeresen elhagyott pontott
}
public int[] Rendez(Graf G) //publikusan elérhető Rendezést végrehajtó metódus
{
n = G.Pontokszama();
Szin = new Paletta[n+1]; //szineket tároló tömb, mint a szinezős bejárásnál
R = new int[n+1]; //pontok rendezett sorrendjét tárolja
for (int p:G) //minden pontott a Szin táblán fehérrel jelöl, kifehérit
Szin[p]=Paletta.Feher;
for (int p:G)
{
if (Szin[p] == Paletta.Feher)
if (!MelyBejar(G,p)) //meghívja MelyBejart()-t és ellenörzi hogy nem-e talált kört.
{
R=null; //ha sikertelen volt akkor talűlt kör, üres R-el kilép
break;
}
}
return R;
{
}
</pre>
===<!--37. -->Erősen összefüggő komponensek, és a transzponált gráf definíciója √===
::u ~ v acsa, ha u ~> v és v ~> u
| |||