جستجوی اول عمق (DFS)

بازگشتی

از مبدأ تا جایی که می‌شود در یک مسیر جلو می‌رود و وقتی به بن‌بست رسید، برمی‌گردد و راه دیگری را امتحان می‌کند.

جستجوی اول عمق از مبدأ تا جایی که می‌تواند در یک مسیر جلو می‌رود. وقتی گره‌ی جاری هیچ همسایه‌ی دیده‌نشده‌ای نداشت (بن‌بست)، کارش تمام است و DFS یک قدم برمی‌گردد تا از گره‌ی قبلی راه دیگری را امتحان کند.

ادامه‌ی توضیح ↓

زمان: O(V + E)
حافظه: O(V) for the recursion
CLRS، بخش ۲۰.۳
هوروویتز–ساهنی، فصل ۶

ورودی:

V=6 · E=7 · src=Uخروجی PDF

گراف جهت‌دار شش‌گره‌ای با یک دور؛ DFS از U عمیق می‌رود، به بن‌بست می‌رسد و برمی‌گردد.

def dfs(graph, src):
seen = set()
parent = {v: None for v in graph}
order = []
visit(graph, src, seen, parent, order)
return order, parent
def visit(graph, u, seen, parent, order):
seen.add(u)
order.append(u)
for v, _ in graph[u]:
if v not in seen:
parent[v] = u
visit(graph, v, seen, parent, order)
return

ناوردا: گره‌هایی که روی پشته‌ی فراخوانی‌اند، مسیری از مبدأ تا گره‌ی جاری در درخت DFS می‌سازند.

شروع اجرا

دیده‌شده
گره‌ی جاری (u)
درخت پیمایش (از parent)
یالِ در حال بررسی

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

src'U'

نارنجی = در همین گام عوض شد

graph dict

'U': [('V', 1), ('X', 1)]
'V': [('Y', 1)]
'W': [('Y', 1), ('Z', 1)]
'X': [('V', 1)]
'Y': [('X', 1)]
'Z': []

Call stack

dfs()خط 1

گام ۱ از ۴۲

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

check
discover
ورودی فعلی (n=6)

نمایش به شکل جدول

n	check	discover
4	5.2	4
8	13.8	8
12	20.8	12
16	28	16
20	35.4	20
24	37.2	24
28	47.2	28

توضیح

ایده

این برگشتن را بازگشت (recursion) خودبه‌خود انجام می‌دهد: هر visit(u) برای همسایه‌ی تازه visit(v) را صدا می‌زند و وقتی آن تمام شد، کار u ادامه پیدا می‌کند. پس پشته‌ی فراخوانی همان مسیر از مبدأ تا گره‌ی جاری است.

گام‌ها

u را به seen اضافه کن (کشف شد).
برای هر همسایه‌ی v از u: اگر v دیده نشده، parent[v] = u را ثبت کن و visit(v) را صدا بزن.
وقتی همه‌ی همسایه‌ها بررسی شدند، u تمام شده است؛ برگرد.

هزینه

هر گره یک بار کشف می‌شود و هر یال یک بار (در گراف بی‌جهت دو بار) بررسی می‌شود: O(V + E). عمق بازگشت در بدترین حالت V است؛ ورودی «زنجیر» را ببین.

کاربردها

DFS پایه‌ی خیلی از الگوریتم‌های گراف است: پیدا کردن دور، مرتب‌سازی توپولوژیک، مؤلفه‌های قویاً همبند و نقاط برش.

در trace به چه چیزی نگاه کنی

گره‌های سیاه دیده شده‌اند و گره‌ی نارنجی همان u در فراخوانی جاری است.
یال‌های آبی درخت DFS‌اند (از parent).
«درخت فراخوانی‌های بازگشتی» دقیقاً همان درخت DFS است: ببین پشته کی عمیق می‌شود و کی برمی‌گردد.
BFS و DFS را روی یک گراف مقایسه کن: BFS پهن جلو می‌رود و DFS عمیق.