სიღრმეში ძებნა (DFS)

BFS ტალღასავით ვრცელდება; DFS ცნობისმოყვარე მკვლევარივით იქცევა. მიმდინარე წვეროდან გადადის ნებისმიერ მოუნახულებელ მეზობელზე და აგრძელებს. როცა წვეროს მოუნახულებელი მეზობელი აღარ დარჩა, უკან ბრუნდება იმ წვეროში, საიდანაც მოვიდა, და მის შემდეგ მეზობელს ცდის.

ერთსა და იმავე ხეზე BFS წვეროებს დონე-დონე ნომრავს, DFS კი მთელ განშტოებას ამთავრებს, სანამ მეორე მხარეს შეეხება.

ბუნებრივი რეალიზაცია რეკურსიაა, ამიტომ აღრიცხვას გამოძახებების სტეკი აკეთებს: void dfs(int v) { used[v] = true; for (int to : g[v]) if (!used[to]) dfs(to); }. ეს BFS-ია, სადაც რიგი სტეკითაა შეცვლილი. DFS უმოკლეს გზებს არ პოულობს, მაგრამ სტრუქტურას ამჟღავნებს: ციკლებს, კომპონენტებს, ამოცანების რიგს, ხიდებს.

ჩაწერე „(v“, როცა v-ში შედიხარ, და „v)“, როცა გამოდიხარ, და მთელი DFS სწორად ჩალაგებულ ფრჩხილებად წაიკითხება. ინტერვალების ენაზე: ნებისმიერი ორი წვეროს [tin, tout] ინტერვალები ან არ იკვეთება, ან ერთი მეორეს შეიცავს; ნაწილობრივ გადაფარვა არასდროს ხდება.

აქედან გამომდინარეობს წინაპრის O(1) შემოწმება: u არის v-ს წინაპარი DFS-ის ხეში ზუსტად მაშინ, როცა tin[u] < tin[v] და tout[v] < tout[u]. ნახაზზე 5-ის ინტერვალი [2, 9] შეიცავს 7-ის [3, 8]-ს, ის კი 9-ის [4, 5]-ს და 1-ის [6, 7]-ს; 2 [10, 13] და 3 [14, 17] ცალკე განშტოებებია.

იგივე ნიშნულები შემდგომ ალგორითმებსაც ამოძრავებს. ტოპოლოგიური სორტირება tout-ის რიგს იყენებს; ხიდები და არტიკულაციის წერტილები tin-ს ადარებს უმცირეს მიღწევად tin-ს; ეილერის შემოვლის ხრიკი კი ყოველ ქვეხეს უწყვეტ შუალედად აქცევს, [tin, tout], პრეფიქსული ჯამებისა თუ სეგმენტების ხისთვის.