Grafer, Bread-first topological sortering

Breadth first har den egenskab at først bliver alle punkter ét hop væk fundet, dernæst 2 hop væk osv... Tænk på det som \'ringe i vandet\', hvor hver ring bliver processeret hver for sig ....

Depth first har den modsatte egenskab, at den forsøger at gå så langt som den kan, før den går baglæns... Her er et træ den bedste analogi...

/Søren Munk Skrøder

Jeg ser at bread/dept-first traversel har præcis de egenskaber du nævner.

Jeg sidder og roder med topologisk sortering efter bogen
\"an introduction to datastructures and algorithms with java\"
af G.W.Rowe, og at sortere giver ikke de samme rækkefølger som at traversere. Kender du noget til det?

/Mikkel

Nope... men jeg kan kigge på det i morgen eftermiddag.. Skal op til eksamen i morgen tidlig ... (Videregående System Udvilking + Videregående Programmering) ... så jeg har først tid i morgen eftermiddag... (Med mindre jeg drikker mig plørefuld bagefter :-)

/Søren Munk Skrøder

en topologisk sortering er en ordning af knuderne, sådan at ingen kant i grafen går fra en knude til en anden knude som står før den i ordningen. Dvs. at enhver vej gennem grafen besøger knuder i samme rækkefølge som de står i en topologisk ordning (hvilket er den egenskab som oftest benyttes).
Læg mærke til at for en graf har en topologisk ordning hvis og kun hvis den er orienteret og acyklisk.
Topologiske ordninger er heller ikke entydige - samme graf kan godt have flere forskellige forskellige topologiske ordninger. Simpelt eksempel: grafen med nabolisten (a,b),(a,c) har både (a,b,c) og (a,c,b) som topologisk ordning.

bearhugx håber det gik godt til eksamen, skal selv op i samme emne tirsdag. (pokkers til en masse økonomi og virksomheds teori #\"¤\"!!!)

delbing, tak for svaret, ser efter søgning på nettet at det er de præcise definitioner på topologisk sortering. Jeg kunne bare stadig godt tænke mig at vide meningen for bread-first vs dept-first sortering.

Efter at have rodet lidt med det kan jeg se at hvis ikke de enkelte verticer blev krydset af med det samme, ville den have givet rækkefølgen i f.h.t. antal veje der gik til verticen, hvor dept-first giver række følgen i f.h.t. antal step fra start vertice.

jeg mente ikke krydset af med det samme, men at antal der peger på de enkelte dekremeres med det samme

bredde først giver måske en mere \"naturlig\" topologisk ordning, da verticernes rækkefølge i sorteringen bedre stemmer overens med grafens topologi, dvs. jo før en vertice står på listen, jo færre verticer er der \"før\" den i grafen. Fra et teoretisk komplicitetssynspunkt er det dog ret uinteressant, da det ikke hjælper noget på worst case tids- eller pladskompleksiteten.
I virkelighedens verden vil bredde først søgning ofte føre til langsommere kørseltider, da ens \"aktive\" datastrukturer bliver langt større, og lokaliteten mellem verticer i datastrukturen er dårlig - ved bredde først skal man i en vis forstand arbejde på alle verticer op til den dybde man er nået til. Dette fører til at cache udnyttes dårligere, og for rigtig store problemer vil det måske endda føre til swapning.
Modsat er dybde først søgning \"unaturlig\" - en vertice der fra start af har indgrad 0 kan godt stå langt nede i den topologiske ordning. Til gengæld arbejder dybde først algoritmer med verticer som typisk er tættere på hinanden i grafen, og derfor er deres repræsentation i hukommelsen også typisk tæt på hinanden, og med langt færre verticer ad gangen i det hele taget. Således kan den data algoritmen arbejder med \"det næste stykke tid\" ofte være i cachen så der kommer færre cache transfers, og cache transfers får langt oftere det næste den skal bruge med.

Hvis topogisk ordning er en subalgoritme kan der selvfølgelig i hovedalgoritmens virkemåde være forhold, som gør at den ene er at foretrække frem for den anden.

*Bøjer sig i støvet for delbings meget brugbare (no joke) svar.*

Tak delbing, jeg må sige at jeg er en lille datamatikerstuderende, du har vel en universitets baggrund. Jeg tror nu ikke jeg vil begynde at rode mig ud i det sidste svar til eksamen (tænk hvis censor vidste lige så meget om det som dig)

Egentlig lidt underligt at definitionen ikke står i en bog som (prøver at) forklare topologisk sortering.

/codemon

[NEWSFLASH] ... Jeg var oppe i videregående systemudvikling (VSU) og videregående programmering (VPrg) .... Jeg fik 8 -

Begrundelsen var, at jeg i VSU var så selvsikker, og ramte nogle væsentlige punkter, at jeg egenligt burde have et 9-tal.... Desværre var min gennemgang af RMI lidt dårlig (jeg er ikke god til at skulle finde nye approches, når jeg først er inde ved det grønne bord), så den trak min karakter ned på et 8-tal ....

Jeg er egenlig meget tilfreds med det :-=)

--SCOREBOARD--
[Teknologi]  6
[VSU/VPrg]  8
[Projekt]    _  (13/7)
[Linux/C++]  _  (27/7)

/Søren Munk Skrøder