Przeszukiwanie grafu w g艂膮b – algorytm DFS

Wi臋kszo艣膰 艣wiata przedstawionego mo偶na przedstawi膰 za pomoc膮 odpowiednich graf贸w. Wynika to z faktu, 偶e wi臋kszo艣膰 obiekt贸w i zdarze艅 jest w mniejszym lub wi臋kszym stopniu ze sob膮 powi膮zana. Cz臋sto zachodzi w praktyce konieczno艣膰 sprawdzenia wszystkich element贸w w danej strukturze lub sprawdzenia powi膮za艅 pomi臋dzy nimi.

Dlatego osoby, kt贸re ju偶 wiedz膮 co to jest graf, pr臋dzej czy p贸藕niej poznaj膮 sposoby przechodzenia graf贸w. W praktyce stosuje si臋 dwa sposoby przej艣cia po wszystkich elementach grafu a bardziej zaawansowane analizy opieraj膮 si臋 na co najmniej jednej z nich. Wspomniane sposoby przej艣cia to algorytm przeszukiwania grafu wszerz (BFS) oraz algorytm przeszukiwania grafu w g艂膮b (DFS), kt贸ry w skr贸cie przedstawi臋 w tym wpisie.

Co znajdziesz w tym wpisie?

Na czym polega algorytm DFS?

Przeszukiwanie grafu w g艂膮b (DFS – Depth-first search), polega na zbadaniu wszystkich kraw臋dzi, kt贸re wychodz膮 z pocz膮tkowego wierzcho艂ka grafu. Nast臋pnie analizowany jest kolejny wierzcho艂ek, do kt贸rego prowadzi jedna z kraw臋dzi i nast臋pny wierzcho艂ek z jego kraw臋dzi, kt贸ry nie zosta艂 odwiedzony i nast臋pny i tak dalej. Natomiast, gdy sprawdzi si臋 ju偶 wszystkie kraw臋dzie jakie wychodz膮 z danego wierzcho艂ka, to wraca si臋 do wierzcho艂ka, z kt贸rego do danego wierzcho艂ka si臋 dosz艂o.

Przyk艂ad przej艣cia po grafie algorytmem DFS

Og贸lna definicja brzmi troch臋 zawile i tak w rzeczywisto艣ci jest, przynajmniej na papierze. 呕eby spos贸b dzia艂ania DFS sta艂 si臋 bardziej jasny, pos艂u偶臋 si臋 przyk艂adem przedstawionym na Wikipedii, tylko troch臋 dok艂adniej i krok po kroku go opisz臋.

Przyk艂ad grafu do analizy dzia艂ania algorytmu DFS z Wikipedii

Spos贸b przej艣cia wskazanego grafu algorytmem DFS mo偶e wygl膮da膰 nast臋puj膮co:

  1. Zaczynamy od wierzcho艂ka A.
  2. Nast臋pnikami wierzcho艂ka A s膮 E,C,B, zapisujemy je do stosu wierzcho艂k贸w do odwiedzenia, a wierzcho艂ek A jako odwiedzony.
    Stos: E,C,B
    Odwiedzone: A
  3. Przechodzimy do wierzcho艂ka B.
  4. Wierzcho艂ek B staje si臋 odwiedzony, a do Stosu dodajemy wierzcho艂ki F oraz D
    Odwiedzone: A,B
    Stos: E,C,F,
    D
  5. Przechodzimy do wierzcho艂ka D.
  6. Wierzcho艂ek D jest odwiedzony, jako 偶e nie ma nast臋pnik贸w nic nie dodajemy do stosu
    Odwiedzone: A,B,D
    Stos: E,C,F
  7. Wracamy do poprzednika, kt贸rym jest wierzcho艂ek B, kt贸ry by艂 ju偶 odwiedzony.
  8. Przechodzimy do wierzcho艂ka F.
  9. Wierzcho艂ek F zosta艂 odwiedzony, a do stosu dodajemy wierzcho艂ek E.
    Odwiedzone: A,B,D,F
    Stos: C,E
  10. Przechodzimy do wierzcho艂ka E, kt贸rego kolejny nast臋pnik (A) zosta艂 ju偶 odwiedzony.
  11. Odwiedzone: A,B,D,F,E
    Stos: C
  12. Wracamy do poprzednika, kt贸rym jest wierzcho艂ek F, kt贸ry by艂 ju偶 odwiedzony.
  13. Wracamy do poprzednika, kt贸rym jest wierzcho艂ek B, kt贸ry by艂 ju偶 odwiedzony.
  14. Wracamy do poprzednika, kt贸rym jest wierzcho艂ek A, kt贸ry by艂 ju偶 odwiedzony.
  15. Przechodzimy do wierzcho艂ka C.
  16. Wierzcho艂ek C staje si臋 wierzcho艂kiem odwiedzonym, a jego nast臋pnikiem jest wierzcho艂ek G.
    Odwiedzone: A,B,D,F,E,C
    Stos: G
  17. Przechodzimy do wierzcho艂ka G.
  18. Wierzcho艂ek G jest odwiedzony, nie ma on nast臋pnik贸w, wi臋c nic nie dodaje si臋 do stosu.
    Odwiedzone: A,B,D,F,E,C,G
    Stos:
  19. Wracamy do poprzednika, kt贸rym jest wierzcho艂ek C, kt贸ry by艂 ju偶 odwiedzony.
  20. Wracamy do poprzednika, kt贸rym jest wierzcho艂ek A, kt贸ry by艂 ju偶 odwiedzony.
  21. Ca艂y graf zosta艂 zbadany i wszystkie wierzcho艂ki odwiedzone.

Na bazie przyk艂adu wygl膮da to klarowniej prawda?

Zastosowania algorytmu DFS

Opr贸cz zastosowa艅 zwi膮zanych z przej艣ciem po ca艂ym grafie, najwi臋ksze zastosowanie algorytm DFS ma w sortowaniu topologicznym, pozwalaj膮cym uporz膮dkowa膰 kolejno艣膰 podejmowanych czynno艣ci.

Algorytm DFS znajduje te偶 zastosowanie w przegl膮daniu tak zwanych drzew gry (opis sytuacji mo偶liwych do osi膮gni臋cia) oraz w rozwi膮zaniach typu brute-force.

Implementacja algorytmu DFS

Zazwyczaj korzysta si臋 z dedykowanych bibliotek w celu skorzystania z algorytmu DFS. Co wi臋cej wykorzystuje si臋 nawet bardziej rozbudowane rozwi膮zania do analizy, lub ca艂e biblioteki do przechodzenia graf贸w, je艣li s膮 konieczne. Zainteresowanych sprawami kodowymi i sposobem wdro偶enia w konkretnych j臋zykach programowania odsy艂am do 藕r贸de艂:

Algorytm DFS a SEO

W kontek艣cie SEO grafy same w sobie s膮 do艣膰 istotne, przynajmniej w teorii. Przede wszystkim dlatego, 偶e istniej膮 grafy link贸w okre艣laj膮ce jak daleko dana witryna linkami znajduje si臋 od warto艣ciowych 藕r贸de艂 w danej tematyce.

Poza tym ka偶dy, kto troch臋 bardziej rozumie czym jest pozycjonowanie stron, zna pot臋g臋 crawlowania serwisu w celu okre艣lenia wszystkich podstron i ich parametr贸w. Mimo, 偶e zazwyczaj si臋 korzysta w tym celu z wyspecjalizowanych narz臋dzi to dzia艂anie crawler贸w opiera si臋 o algorytmy DFS i BFS.

Dodatkowo znajomo艣膰 algorytmu DFS jest przydatna dla bardziej wysublimowanych sposob贸w znajdowania najkr贸tszej 艣cie偶ki w grafie. Z punktu widzenia SEO i marketingu ma to zastosowanie w okre艣laniu jak wiele klikni臋膰 jest potrzebnych by do艣膰 do danego zasobu. Oczywi艣cie nie robi si臋 tego r臋cznie, tylko za pomoc膮 odpowiednich narz臋dzi wykorzystuj膮cych tego typu algorytmy.

Podsumowanie algorytmu DFS

Grafy s膮 wok贸艂 nas i konieczno艣膰 ich przeszukiwania dopada nas na ka偶dym kroku, w sieciach komputerowych, logistyce, stronach internetowych, procesach w kt贸rych uczestniczymy. Dlatego warto zna膰 mechaniki pozwalaj膮ce na eksploracj臋 graf贸w by bli偶ej pozna膰 opis matematyczny 艣wiata, kt贸ry nas otacza. Mam nadziej臋, 偶e ten wpis o algorytmie DFS cho膰 troch臋 si臋 do tego dla Ciebie przyczyni艂. Je艣li chcia艂by艣 si臋 podzieli膰 mo偶liwym zastosowaniem tego algorytmu, kt贸re nie zosta艂o uwzgl臋dnione, serdecznie zapraszam do pozostawienia komentarza!

Mo偶e Ci si臋 r贸wnie偶 spodoba

Dodaj komentarz

Tw贸j adres email nie zostanie opublikowany. Pola, kt贸rych wype艂nienie jest wymagane, s膮 oznaczone symbolem *