Plasate
Așteaptă să fie plasate
Muchii verificate

  • Curent
  • Libere sau în vizitare
  • Plasate
  • Ciclu

Mai multe despre sortarea topologică

Sortare topologică

Șosetele înaintea pantofilor, fundația înaintea zidurilor, un curs înaintea cursului care are nevoie de el. O sortare topologică pune nodurile unui graf cu muchii cu sens unic pe un rând în care fiecare muchie indică înainte. Alegeți algoritmul lui Kahn sau metoda DFS și avansați pas cu pas ca să vedeți cum crește ordinea, apoi adăugați un ciclu ca să vedeți de ce nicio ordine nu mai este posibilă. Apăsați Redare pentru a urmări cum crește ordinea sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Fiecare muchie are sens unic, după cum arată săgeata: gândiți-vă la ea ca la "acesta vine înaintea aceluia". Alegeți metoda: algoritmul lui Kahn plasează întâi nodurile fără muchii de intrare, iar numărul de pe fiecare nod arată câte muchii de intrare mai are; metoda DFS pune fiecare nod în față după ce tot ce urmează după el este plasat. Rândul de sub graf este ordinea de până acum. Bifați Adaugă un ciclu ca să vedeți cum îl găsește fiecare metodă. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Alegeți algoritmul lui Kahn sau metoda DFS.
  2. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
  3. Urmăriți cum crește ordinea sub graf. Bifați Adaugă un ciclu ca să vedeți cum îl găsește fiecare metodă.

Algoritmul lui Kahn

Numărați, pentru fiecare nod, câte muchii indică spre el. Un nod fără niciuna nu depinde de nimic, deci poate fi primul. Plasați un astfel de nod și eliminați-i muchiile de ieșire: nodurile spre care indicau au acum cu o muchie de intrare mai puțin, iar unele pot ajunge la zero și devin libere. Continuați să plasați noduri libere până nu mai rămâne niciunul. Dacă unele noduri nu au devenit niciodată libere, ele se așteaptă unele pe altele într-un ciclu și nu există nicio ordine topologică.

Metoda DFS

Rulați o căutare în adâncime din fiecare nod nevizitat. Un nod este terminat când tot ce se poate atinge din el este terminat, deci tot ce trebuie să vină după el este deja plasat. Puneți fiecare nod terminat în fața ordinii, iar ordinea iese corectă. Dacă, urmând o muchie, căutarea ajunge la un nod în care se află încă, acea muchie închide un ciclu și, din nou, nu există nicio ordine.

Întrebări frecvente

Ce este o sortare topologică?

O ordonare a nodurilor unui graf orientat în care fiecare muchie merge de la un nod anterior la unul ulterior. Dacă muchiile înseamnă "trebuie să vină înainte de", este o ordine în care pot fi făcute toate sarcinile.

Când există o ordine topologică?

Exact atunci când graful nu are niciun ciclu orientat: este un graf orientat aciclic, sau DAG. Cu un ciclu, fiecare nod de pe el ar trebui să vină înaintea lui însuși.

Este ordinea topologică unică?

De obicei nu. Când două noduri nu sunt legate printr-un lanț de muchii, oricare dintre ele poate fi primul, deci un graf poate avea multe ordini valide. Algoritmul lui Kahn și metoda DFS dau adesea ordini diferite.

Cât de rapidă este o sortare topologică?

Ambele metode examinează fiecare nod și fiecare muchie de un număr fix de ori, deci munca crește cu numărul de noduri plus numărul de muchii.

Este graful meu trimis undeva?

Nu. Graful este creat și sortat în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor