BFS و DFS دو راهِ پیمایشِ گراف‌اند. BFS با صف، همسایه‌هایِ نزدیک‌تر از نظرِ تعدادِ یال را پیش‌تر بررسی می‌کند؛ DFS یک شاخه را تا جایی که قرارداد اجازه می‌دهد دنبال می‌کند و برمی‌گردد. در گرافِ بی‌وزن، نخستینِ مسیرِ کشف‌شدهٔ BFS کمترینِ تعدادِ یال را دارد؛ مسیرِ نخستِ DFS الزاماً چنین نیست.
یک گراف برایِ هر دو روش
گرافِ جهت‌دارِ آموزشی، S→AوS→B، A→C، C→D، D→TوD→A، وB→Tدارد. Uگرهِ جداست. ترتیبِ همسایه‌هایِSاولAبعدB و برایِDاولTبعدAاست. چرخهٔA→C→D→A عمداً وجود دارد تا روشن شود چرا ثبتِ visited لازم است. در این مثال وزنِ متفاوتی به یال‌ها نداده‌ایم؛ طولِ مسیر تعدادِ یال است.
هر گره هنگامِ کشف علامت می‌خورد: در BFSپیش از واردشدن به صف ودرDFSابتدایِ ورودِ تابع. parentفقط در نخستینِ کشف تعیین می‌شود. بدین‌ترتیب، یالِ برگشتیِD→Aباعثِ تکرارِ بی‌پایانِ همان شاخه نمی‌شود. هدفِ این کد یافتنِ همهٔ چرخه‌ها نیست؛ visitedفقط پیمایشِ محدود را کنترل می‌کند.
BFS با صفِ FIFO چه ترتیبی می‌سازد؟
Sرا برمی‌داریم وAوBرا به صف می‌افزاییم. با برداشتنِA، Cدر انتهایِ صف می‌رود؛ Bزودتر ازCبرداشته می‌شود وTرا کشف می‌کند. بعدC، Dرا اضافه می‌کند. ترتیبِ برداشتنِ گره‌ها در همین داده S،A،B،C،T،Dاست؛ ترتیبِ شناسه‌هایِ واژگانی نیست، بلکه محصولِ صف و فهرستِ همسایه‌هاست.
parentِTبرابرِB وparentِBبرابرِSاست، پس مسیرِ هدف S→B→Tدویال دارد. فاصله‌هایِ لایه‌ای S=۰، AوB=۱، CوT=۲ وD=۳هستند. چون گره‌ها به ترتیبِ فاصلهٔ تعدادِ یال کشف می‌شوند، نخستینِ کشفِ هدف در این قرارداد مسیرِ کم‌یال می‌دهد.
DFS چرا زودتر یک مسیرِ بلندتر را می‌بیند؟
DFSازSبهA، سپسC، DوTمی‌رود؛ پس نخستینِ مسیرِ هدف S→A→C→D→Tچهاریال دارد. بعد از برگشت، یالِD→Aبه گرهِ دیده‌شده می‌رسد و نادیده گرفته می‌شود؛ در پایان شاخهٔBهم دیده می‌شود، اما parentِTرا بازنویسی نمی‌کند. ترتیبِ کامل S،A،C،D،T،Bاست.
| کمیتِ همین گراف | BFS | DFS با ترتیبِ اصلی |
|---|---|---|
| مسیرِ هدف | S→B→T | S→A→C→D→T |
| تعدادِ یالِ مسیر | ۲ | ۴ |
| گره‌هایِ دیده‌شده | ۶ | ۶ |
| یال‌هایِ درختِ کشف | ۵ | ۵ |
این جدول مسابقهٔ سرعت نیست؛ دو اجرا درختِ کشف و مسیرِ متفاوت می‌سازند. DFSهم می‌تواند گرهٔ هدف را پیدا کند، اما ادعایِ کمترینِ مسیر برایِ نخستینِ کشفش از این روش به دست نمی‌آید.
ترتیبِ همسایه‌ها را عوض کنیم
فهرستِ همسایه‌هایِ هر گره را برعکس وDFSرا دوباره اجرا می‌کنیم. این بار درS، Bپیش ازAدیده می‌شود وهدف ازمسیرِدویالی پیدا می‌شود. نتیجهٔ بهترِ این ترتیب، ضمانتِ عمومیِ کوتاه‌ترینِ مسیرِ DFSنیست. برایِ بازتولیدِ گزارش، ترتیبِ فهرست‌ها را کنارِ نامِ الگوریتم ثبت کنید؛ استفاده از یک مجموعهٔ بی‌ترتیب می‌تواند بازدید را عوض کند.
یک شمارندهٔ مستقل هم تمامِ مسیرهایِ سادهٔ کوچک ازSبهTرا می‌سازد. کمترینِ تعدادِ یالِ آن۲است و باBFSبرابر می‌شود. این oracleعمداً برایِ گرافِ کوچک است؛ شمارشِ مسیرها می‌تواند در گرافِ بزرگ بسیار پرهزینه شود و جایگزینِ عملیِ عمومیِ BFSنیست.
درختِ پیمایش، همهٔ یال‌هایِ گراف نیست
گراف هفت یال دارد، اما درختِ کشفِ هر دو روش پنج یال: برایِ هر گرهٔ تازهٔ غیر ازمبدأ، یک parent. یالِ برگشتی و یالی که به گرهِ قبلاً کشف‌شده می‌رسد، به درخت اضافه نمی‌شود. خروجیِ یک تابعِ traversalِ گره‌محور را فهرستِ تمامِ یال‌هایِ ورودی ننامید.
UازSدسترس‌پذیر نیست و مسیرش nullاست؛ این به معنیِ نداشتنِ خودِ گره در گراف نیست. هر دو روش فقط بخشِ دسترس‌پذیر ازمبدأِ اعلام‌شده را می‌پیمایند. DFSِ این فایل بازگشتی و مخصوصِ تمرینِ کوچک است؛ عمقِ بزرگ می‌تواند به محدودیتِ پشتهٔ Pythonبرسد. هیچ اندازه‌گیریِ زمان یا حافظه و هیچ اجرایِ NetworkXانجام نشده است.
برایِ هزینهٔ متفاوت، مسئله را عوض کنید
اگر یک یال هزینهٔ۱۰و مسیرِ سه‌یالی مجموعِ۵داشته باشد، کمترینِ تعدادِ یال هدفِ مناسبی برایِ کمترینِ هزینه نیست. دایکسترا این تفاوت را با مثالِ وزن‌دار اجرا می‌کند. گرافِ دانش هم دربارهٔ معنایِ رابطه و شناسه است؛ پیمایشِ درست، حقیقتِ یال‌ها را اثبات نمی‌کند. برایِ مبانی به آموزشِ هوشِ مصنوعی بروید و برایِ نیازِ پاسخ‌گویی، خروجیِ موردِ انتظار را در راهکارهایِ اپرا مشخص کنید.
فایل تمرین و منبع
دو پیمایشِ واقعی و parent و کنترلِ همهٔ مسیرهایِ ساده؛ Python · ترتیبِ بازدید، مسیرِ۲و۴یالی و اثرِ عوض‌کردنِ ترتیبِ همسایه‌ها
- NetworkX؛ BFSِ گره‌محور و تفاوتِ یال‌هایِ درخت با همهٔ یال‌هایِ گراف
- NetworkX؛ پیمایشِ عمقی، مبدأ و ترتیبِ همسایه‌ها؛ کتابخانه اینجا اجرا نشده است
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.