søger et algoritme navn

Tags:    c++

Hej
Jeg har lige et spørgsmål mere!
Jeg har en graf som jeg skal have sorteret.
Grafen er; uvægtet, cyklisk (i klynger), og retningsbestemt.

Har så siddet og søgt lidt rundt og fundet ud af at jeg kan kombinere topologisk sortering med en depth-first undersøgelse af hvorvidt der er cyklusser.

Spørgsmålet til forummet er om den kombination er opkaldt efter en klog mand eller på anden måde har fået et navn. Jeg har ikke været i stand til at finde noget på nettet.

Jeg fandt dog et stykke metaprogrammering:
http://www.eecs.harvard.edu/nr/cs152/progs/tsort.uml

Mvh
Carsten

PS: Måske har jeg misforstået at depth-first i virkeligheden bare er en ekstra feature man kan smide i sin topologiske sortering hvis den er nødvendig. Men vil bare tjekke om det er navngivet, da det er til en skriftlig opgave.



3 svar postet i denne tråd vises herunder
0 indlæg har modtaget i alt 0 karma
Sorter efter stemmer Sorter efter dato
Ok. Takket været Robert Sedgewick har jeg luret at det handler om "Strongly connected components" og første gang blev skrevet om i 1972 af R. E. Tarjan.

Carsten

http://en.wikipedia.org/wiki/Strongly_connected_component

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm



Indlæg senest redigeret d. 19.05.2008 15:01 af Bruger #12570
du kan ikke topology sorterer noget der er cyklisk. hvis det ikke er cyclisk men acyclisk så det en DAG(directed acyclic graph), såvidt jeg ved :) og tror bare den heder unweigthed DAG når det uden vægt.



du kan ikke topology sorterer noget der er cyklisk. hvis det ikke er cyclisk men acyclisk så det en DAG(directed acyclic graph), såvidt jeg ved :) og tror bare den heder unweigthed DAG når det uden vægt.


Jep. Jeg fandt ud af det. Må hellere lukke tråden.

EDIT: Arg shit kom til at poste og nu kan jeg ikke give point. Så vil jeg nøjes med at sige tak :)



Indlæg senest redigeret d. 19.05.2008 15:28 af Bruger #12570
t