Hoppa till huvudinnehåll

Depth First Search , Exempel

Låt oss se hur Depth First Search (DFS) fungerar med ett konkret exempel.
Vi använder en odirected graf (icke-riktad graf) med 5 noder.

Startpunkt​

Vi börjar från nod 0.

DFS-algoritmen startar med att:

  1. Lägga noden i besökta-listan
  2. Lägga alla dess noder som är anslutna (grannar) i stacken
image

Steg för steg​

Steg 1​

  • Besök nod 0
  • Lägg till i besökta-listan
  • Lägg grannar i stacken
image

Steg 2​

  • Besök noden överst i stacken, dvs. nod 1
  • Titta på dess grannar
  • Nod 0 är redan besökt, så vi går vidare till nod 2
image

Steg 3​

  • Besök nod 2
  • Nod 2 har en obesökt granne, nämligen nod 4
  • Lägg nod 4 överst i stacken och besök den
image

Steg 4​

  • Nod 4 är nu besökt
  • Därefter besöker vi nod 3
  • Nod 3 har inga fler obesökta grannar
image

Traversering klar!​

När vi har besökt sista noden (nod 3) och den inte har några obesökta grannar,
är vi klara med DFS-traverseringen av grafen.

Slutresultat​

DFS har nu gått igenom alla noder så långt det gick i varje gren innan den backade.

  • Startnod: 0
  • Besökta noder i ordning:
    0 → 1 → 2 → 4 → 3