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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Փնտրում դեպի խորություն
Depth-first-tree.svg
Տեսակ uninformed search
Տվյալների կառուցվածք Գրաֆ
Օգտագործում է գրաֆ


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

Խորության փնտրման ալգորիթմ[խմբագրել | խմբագրել կոդը]

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

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

Ֆունկցիա DFS (պարամետր — գագաթ )

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

Ոչ ռեկուրսիվ տարբերակ[խմբագրել | խմբագրել կոդը]

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)

Կիրառություն[խմբագրել | խմբագրել կոդը]