موضوع مقاله: پیمایش گراف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پیمایش گراف | مقدمه: الگوریتم درخت پوشای مینیمم( prim )و الگوریتم کوتاه‌ترین مسیرها از مبدأ(source) واحد( دایجسترا )،از ایده ای مشابه جستجوی اول سطح استفاده می‌کنند. | ## بخش 1: پیمایش گراف | گراف (G=(V,E و رأس مبدأ مشخص s داده شده‌است، جستجوی اول سطح به صورت اصولی یال‌های G را برای پیدا کردن رئوسی که از s قابل دستیابی اند، مرور می‌کند. این الگوریتم فاصله (کمترین تعداد یال‌ها) هر رأس قابل دستیابی از s را محاسبه می‌کند. همچنین «درخت اول سطح» ریشهٔ s که شامل تمامی رئوس قابل دستیابی می‌باشد را تولید می‌کند. علت این که این الگوریتم، جستجوی اول سطح نامیده شده، این است که یک مرز بین رئوس کشف شده و رئوس کشف نشده به طور یکنواخت در راستای سطح مرز عبوری توسعه می‌دهد. به عبارت دیگر همهٔ رأس‌ها ی با فاصلهٔ k از s را قبل از این که رئوس با فاصلهٔ k+l را کشف کند، کشف می‌کند. یک رأس اولین باری که در طول جستجو ملاقات می‌گردد، کشف می‌شود، که در آن زمان غیر سفید می‌شود، بنابراین رئوس سیاه و خاکستری کشف شده‌اند اما جستجوی اول سطح بین آن‌ها تمایز قائل می‌شود تا اطمینان حاصل کند که جستجو به شکل اول سطح پیش می‌رود. اگر (E (u,v و رأس u سیاه باشد آنگاه رأس v سیاه یا خاکستری است؛ به عبارت دیگر همهٔ رئوس مجاور رئوس سیاه کشف شده‌اند. رئوس خاکستری ممکن است رأس مجاور به رنگ سفید داشته باشند؛ آن‌ها مرز بین رئوس کشف شده و کشف نشده را نشان می‌دهند. جستجوی اول سطح یک درخت اول سطح را می‌سازد، که در آغاز تنها شامل ریشه‌است که رأس منبع s می‌باشد. | ## بخش 2: پیمایش گراف | هر وقت رأس سفید v در مرحلهٔ پویش لیست همجواری رأس کشف شده u، کشف شود رأس v‌و یال (u,v)‌به درخت اضافه می‌شوند. از آن جایی که هر رأس حداکثر یک بار کشف می‌شود، حداکثر یک پدر دارد رابطهٔ جد و نتیجه (نسل) در درخت جستجوی اول سطح به شکل معمول نسبت به ریشهٔ s تعریف می‌شود: اگر u‌در مسیری از درخت از s به v واقع باشد آنگاه u جد v‌و v نتیجهٔ u است. روال جستجوی اول سطح (BFS) زیر فرض می‌کند که گراف ورودی (G=(V,E با استفاده از لیست همجواری نمایش داده می‌شود. اگر u فاقد ماقبل باشد (برای مثال u=s یا u کشف نشده با شد) آن گاه فاصله از منبع s تا رأس u که توسط الگوریتم محاسبه می‌شود در d[u] ذخیره می‌گردد. جستجوی اول عمق استراتژی ای که به وسیلهٔ جستجوی اول عمق دنبال می‌شود، همان طور که نامش اشاره دارد، جستجوی عمیق تر در گراف تا زمانی که ممکن است، می‌باشد. این فرایند ادامه می‌یابد تا زمانی که همهٔ یال‌ها ی قابل دسترسی از مبدأ صلی s را کشف کنیم. اگر رأس‌های کشف نشده‌ای باقی بمانند، آن گاه یکی از رئوس به عنوان مبدأ جدید انتخاب می‌گردد و جستجو از آن مبدأ تکرار می‌شود. همانند جستجوی اول سطح، هنگامی که رأس v در طی پویش لیست همجواری رأس u که قبلاً کشف شده، کشف می‌گردد جستجوی اول عمق این رویداد را با قرار دادن u در فیلد ماقبل v یعنی ثبت می‌کند. بر خلاف جستجوی اول سطح که زیر گراف ماقبل آن، یک درخت را تشکیل می‌دهد، زیرگراف ماقبل تولید شده به وسیلهٔ جستجوی اول عمق ممکن است از چندین درخت تشکیل شده باشد، چون جستجو ممکن است از چند مبدأ تکرار شود. | ## بخش 3: پیمایش گراف | بنابراین زیرگراف ماقبل جستجوی اول عمق اندکی متفاوت با زیرگراف ماقبل جستجوی اول سطح تعریف می‌شود: فرض می‌کنیم که زیرگراف ماقبل جستجوی اول عمق، جنگل اول عمق تشکیل شده از چندین درخت اول عمق را شکل می‌دهد. هر رأس در آغاز سفید است، وقتی در جستجو کشف می‌شود، خاکستری می‌گردد و وقتی خاتمه می‌یابد، سیاه رنگ می‌شود، به عبارت دیگر وقتی لیست همجواری آن به‌طور کامل بررسی می‌گردد. این تکنیک تضمین می‌کند که هر رأس در دقیقاً یک درخت اول عمق خاتمه می‌یابد که به موجب آن درخت‌ها متمایز هستند. علاوه بر ایجاد جنگل اول عمق، جستجوی اول عمق هر رأس را برچسب دهی زمانی نیز می‌کند. هر رأس v دارای دو برچسب زمانی می‌باشد: وقتی رأس v در ابتدا کشف می‌گردد (خاکستری می‌گردد) اولین برچسب d]v] ثبت می‌شود و دومین برچسب زمانی f[v] زمانی ثبت می‌شود که جستجو، بررسی لیست همسایگی v را خاتمه دهد (و v را سیاه رنگ کند) این برچسب‌های زمانی در بسیاری از الگوریتم‌های گراف استفاده می‌شوند و به‌طور کلی در استدلال در مورد رفتار جستجوی اول عمق مفید هستند. روال جستجوی اول عمق(DFS) زیر، زمان کشف رأس را در متغیر d]v] و زمان خاتمهٔ رأس u را در متغیر f]u] ثبت می‌کند. این برچسب‌های زمانی اعداد صحیح بین ۱ تا ۲|V| هستند، چون برای هر یک از |V| رأس یک رویداد کشف و یک رویداد خاتمه وجود دارد. شاید اساسی‌ترین ویژگی جستجوی اول عمق این است که زیرگراف ما قبل به راستی یک جنگل از درخت‌ها را شکل می‌دهد، چون ساختار درخت‌ها ی اول عمق، بازتاب دهندهٔ ساختار فراخوانی بازگشتی DFS_Visit می‌باشد. به عبارت دیگر اگر و فقط اگر DFS_Visit)v) در طی جستجوی لیست همجواری u فراخوانی شده باشد، به علاوه، رأس v نتیجهٔ رأس u در جنگل اول عمق است اگر و فقط اگر v در طی زمانی که u خاکستری است کشف شود. | ## جمع‌بندی | اگر کشف رأس u را با پرانتز چپ«u)» و خاتمه را به وسیلهٔ پرانتز راست «(u» نشان دهیم، آن گاه کشف‌ها و خاتمه‌ها یک عبارت خوش فرم در جمله ایجاد می‌کنند که پرانتزها به‌طور صحیح تو در تو می‌باشند.