Topologikus sorrend

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

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.

Directed acyclic graph.png
A bal oldalon látható gráfnak több topologikus rendezése is létezik, köztük:
  • 7,5,3,11,8,2,10,9
  • 7,5,11,2,3,10,8,9
  • 3,7,8,5,11,10,9,2
  • 3,5,7,11,10,2,8,9

Forrás[szerkesztés | forrásszöveg szerkesztése]

http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf