Փնտրում դեպի խորություն

Փնտրում դեպի խորություն Գրաֆը շրջանցելու մեթոդներից մեկը։ Ալգորիթմի ստրատեգիան, ինչպես հետևում է անվանումից՝ գնալ դեպի խորություն որքան որ հնարավոր է։ Որոնման ալգորիթմը նկարագրվում է ռեկուրսիվ՝ հերթով վերցվում է հանգույցից դուրս եկող բոլոր արմատները։ Եթե կողը տանում է դեպի չբացահայտված հանգույցը, ապա ալգորիթմը վերսկսում ենք այդ հանգույցից, հետո վերադառնում ենք և վերցնում ենք մյուս արմատները։ Վերադարձը կատարվում է այն ժամանակ, երբ դիտարկվող գագաթում չեն մնացել կողեր, որոնք տանում են դեպի չբացահայտված գագաթներ։ Եթե ալգորիթմի ավարտից հետո դեռ մնացել են չբացահայտված հանգույցներ, ապա ալգորիթմը պետք է կիրառել չբացահայտված հանգույցներից որևէ մեկից սկսած։

Խորության փնտրման ալգորիթմ

Տրված է գրաֆ $G=(V,E)$, որտեղ $V$-ն գրաֆի գագաթների բազմությունն է, $E$-ն՝ կողերի բազմությունը։ Ենթադրենք, որ սկզբում բոլոր գագաթները ներկված են սպիտակ գույնով։ Կատարենք հետևյալ քայլերը։

1. Անցնենք բոլոր գագաթներով $v\in V$։
   • Եթե $v$ գագաթը սպիտակ է, կատարում ենք նրա համար DFS(v).

Ֆունկցիա DFS (պարամետր — գագաթ $u\in V$)

1. Ներկում ենք $u$ գագաթը մոխրագույն գույնով։
2. Ինչ-որ $w$ գագաթ,որը $u$ գագաթի հարևանն է և ներկված է սպիտակ գույնով, ռեկուրսիվ կատարում ենք DFS(w) ֆունկցիան։
3. Ներկում ենք $u$ գագաթը սև գույնով։

Ոչ ռեկուրսիվ տարբերակ

DFS-ի ոչ ռեկուրսիվ օգտագործման տարբերակը։

1 ֆունկցիա DFS-iterative(G,v)։
2 S սթեք է
3 S.push(v)
4 while S դատարկ չէ
5  v = S.pop()
6  if v եթե բացահայտված չէ ԵՎ սթեքի մեջ չէ։
7  Նշել v, որպես բացահայտված
8  for all բոլոր արմատների համար vմինչև w in G.հարևանարմատ(v) do
9   if w բացահայտված չէ         ։    S.push(w)

Կիրառություն

Պատկեր:MAZE 30x20 DFS.ogv Կաղապար:Արտաքին հղումներ