Skierowany graf acykliczny
![]() | Ten artykuł od 2023-11 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/39/Directed_acyclic_graph_3.svg/220px-Directed_acyclic_graph_3.svg.png)
Skierowany graf acykliczny (ang. directed acyclic graph, DAG) – graf skierowany, który nie posiada cyklów skierowanych. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych.
Przykład
Jeśli chcemy przedstawić pewne obliczenia za pomocą drzewa, może ono się wykładniczo rozrosnąć:
b = a + a; c = b + b; d = c + c e = d + d; f = e + e; g = f + f h = g + g
Drzewo dla h
ma już 128 liści, operowanie na tej postaci nie jest więc wygodne. Z drugiej strony dla ogólnych grafów skierowanych trudno jest stworzyć algorytm wyliczania wartości wyrażeń, gdyż łatwo jest się zapętlić.
Jeśli skorzystamy ze skierowanych grafów acyklicznych i programowania dynamicznego, otrzymamy wyliczenia (jeżeli a=10
):
h = g + g (brak g, wyliczmy najpierw g) g = f + f (brak f, wyliczmy najpierw f) f = e + e (brak e, wyliczmy najpierw e) e = d + d (brak d, wyliczmy najpierw d) d = c + c (brak c, wyliczmy najpierw c) c = b + b (brak b, wyliczmy najpierw b) b = a + a = 10 + 10 = 20 c = b + b = 20 + 20 = 40 d = c + c = 40 + 40 = 80 e = d + d = 80 + 80 = 160 f = e + e = 160 + 160 = 320 g = f + f = 320 + 320 = 640 h = g + g = 640 + 640 = 1280
Na zasadzie skierowanych grafów acyklicznych działa m.in. algorytm unifikacji, działający w czasie liniowym (a którego wynik przedstawiony jako drzewo ma potencjalnie wykładniczy rozmiar).
Zastosowania
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/EgyptianPtolemies2.jpg/220px-EgyptianPtolemies2.jpg)
Grafy takie, mają szerokie zastosowania w obliczeniach numerycznych, przetwarzaniu potokowym (np. projektowaniu procesorów), tworzeniu układów kombinacyjnych z bramek logicznych, kompresji, kompilatorach, diagramach przepływu, przepływie danych czy zasobów (transport, energia elektryczna, woda). Grafy takie mogą również opisywać porządek częściowy.
Spójny DAG w którym istnieje jeden wyróżniony wierzchołek, do którego nie ma krawędzi wchodzących (tzw. korzeń), można zmienić na drzewo, które posiada powtarzające się poddrzewa. Operacje odwrotną (wyszukiwanie powtarzających się poddrzew w drzewie, i zamienianie go w DAG), wykorzystuje się m.in. w kompilatorach przy tzw. eliminacji wspólnych podwyrażeń. Grafy z wieloma wierzchołkami nieposiadającymi krawędzi wchodzących, można sprowadzić praktycznie do wymaganej postaci poprzez dodanie nowego wierzchołka, który sam nie posiada krawędzi wchodzących, a krawędzie wychodzące kierują do rzeczonych wierzchołków (tzw. początkowych).
Bibliografia
- Thomas H. Cormen, Leiserson Chalres E., Rivest Ronald L., Stein Clifford: Introduction to Algorithms. Massachusetts Institute of Technology, 2009, s. 589-683. ISBN 978-0-262-03384-8.
Zobacz też
- sortowanie topologiczne
- drzewo (informatyka)