Grafiek serialisasie

Question

Ek is op soek na'n eenvoudige algoritme om te se serialize'n gerigte grafiek.In die besonder, ek het'n stel van lêers met interafhanklikhede op hul uitvoering orde, en ek wil om uit te vind die korrekte volgorde op die stel van tyd.Ek weet dit moet'n redelik algemene ding om te doen - opstellers doen dit al die tyd - maar my google-fu is swak vandag.Wat is die "go-te" algoritme vir hierdie?

Answer 1

Topologiese Sorteer (vanuit Wikipedia):

  

In grafiekteorie, 'n topologiese aard of   topologiese bestel van 'n gerigte   asikliese grafiek (DAG) is 'n lineêre   bestel van sy knope waarin elke   knoop kom voor al die nodes om wat   dit het uitgaande kante. Elke DAG het   een of meer topologiese vorme.

Pseudo-kode:

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)

Answer 2

Ek sou verwag gereedskap wat nodig hierdie eenvoudig die boom loop in 'n diepte-eerste wyse en wanneer hulle 'n blaar getref, net verwerk dit (bv saamstel) en verwyder dit uit die grafiek (of merk dit as verwerk, en behandel nodes met al die blare verwerk as blare).

As solank dit 'n DAG, hierdie eenvoudige stapel gebaseer stap moet triviale wees.

Answer 3

As die grafiek bevat siklusse, hoe kan daar bestaan nie toegelaat word om die uitvoering van bestellings vir jou lêers?Dit lyk vir my dat indien die grafiek bevat siklusse, dan is jy het nie'n oplossing, en dit is berig korrek deur die bo-algoritme.

Answer 4

Ek het vorendag gekom met 'n redelik naïef rekursiewe algoritme (pseudokode):

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

Die grootste probleem met hierdie is dat dit het geen vermoë om sikliese afhanklikhede op te spoor - dit kan gaan in oneindige rekursie (dws stapel oorloop ;-p). Die enigste manier om dit wat ek kan sien sal wees om die rekursiewe algoritme flip in 'n Interative een met 'n handleiding stapel, en met die hand gaan die stapel vir herhaalde elemente.

Enigiemand het iets beter?