Topologikus sorrend
Legyen D=(V,A) irányított gráf. A gráf csúcsainak akkor és csak akkor van olyan sorrendje, amiben minden él előrefelé vezet, ha aciklikus (irányított körmentes gráf). Az ilyen sorrendet topologikus sorrendnek nevezik.
Algoritmus a topologikus sorrend meghatározására [szerkesztés]
Az algoritmus egy adott s pontból indul. Erről vagy előre ismert, hogy minden pont elérhető belőle, vagy az algoritmus adja hozzá. A gráfba még beteszi az összes sv élt, ahol v eleme V.
Minden pontra két címkét tart számon. Az egyik címke azt mutatja, hogy a pont elért-e, és ha igen, akkor melyik csúcsból. A másik címke pedig azt, hogy a csúcs átvizsgált-e, vagy sem. Kezdetben s elért, nem átvizsgált.
Amíg van elért, de nem átvizsgált pont, addig ismétli a következőket:
Kiválasztja a legkésőbb elért, nem átvizsgált u pontot. Eldönti, hogy van-e egy uv él a gráfban, aminek v végpontja nem elért. Ha talál ilyet, akkor átállítja v címkéjét: v elért az u pontból. Ha nem talál, akkor átállítja u címkéjét: u átvizsgált, és feljegyzi a címkébe, hogy éppen hányadik lépésnél tart.
Az átvizsgálási sorrend topologikus sorrendet ad. Ha az s pont nem volt az eredeti gráfban, akkor törli.
Megfelelő adatstruktúrával mindez az élszámmal arányos időt vesz igénybe.
 |
A bal oldalon látható gráfnak több topologikus rendezése is létezik, köztük:
|
Forrás [szerkesztés]
http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf
