پیمایش گراف

پیمایش گراف به معنی بازدید از تک‌تک رأس‌های گراف به نحوی خاص است. مسئلهٔ پیمایش درخت حالت خاصی از پیمایش گراف است. برای این کار الگوریتم‌هایی چند هست.

جستجوی اول سطح

مقالهٔ اصلی: الگوریتم جستجوی اول سطح

جست و جوی اول سطح (Breadth_first search) یکی از ساده‌ترین الگوریتم‌ها برای جست و جوی گراف و نوعی پایه برای بسیاری از الگوریتم‌های مهم گراف است. الگوریتم درخت پوشای مینیمم( prim )و الگوریتم کوتاه‌ترین مسیرها از مبدأ(source) واحد( دایجسترا )،از ایده ای مشابه جستجوی اول سطح استفاده می‌کنند. گراف (G=(V,E و رأس مبدأ مشخص s داده شده‌است، جستجوی اول سطح به صورت اصولی یال‌های G را برای پیدا کردن رئوسی که از s قابل دستیابی اند، مرور می‌کند. این الگوریتم فاصله (کمترین تعداد یال‌ها) هر رأس قابل دستیابی از s را محاسبه می‌کند. همچنین «درخت اول سطح» ریشهٔ s که شامل تمامی رئوس قابل دستیابی می‌باشد را تولید می‌کند. برای هر رأس v قابل دستیابی از s مسیر واقع در درخت جستجوی اول سطح از s به v متناظر با کوتاه‌ترین مسیر (shortest path) از s‌به v در G می‌باشد، به عبارت دیگر مسیری شامل کمترین تعداد یال. الگوریتم برای هر دو گراف جهت دار و بدون جهت اعمال می‌شود.

علت این که این الگوریتم، جستجوی اول سطح نامیده شده، این است که یک مرز بین رئوس کشف شده و رئوس کشف نشده به طور یکنواخت در راستای سطح مرز عبوری توسعه می‌دهد. به عبارت دیگر همهٔ رأس‌ها ی با فاصلهٔ k از s را قبل از این که رئوس با فاصلهٔ k+l را کشف کند، کشف می‌کند.

در ادامه جستجوی اول سطح، هر رأس را با سفید، خاکستری یا سیاه رنگ می‌کند. همهٔ رئوس در ابتدا سفید هستند امات ممکن است بعد خاکستری و آن گاه سیاه شوند. یک رأس اولین باری که در طول جستجو ملاقات می‌گردد، کشف می‌شود، که در آن زمان غیر سفید می‌شود، بنابراین رئوس سیاه و خاکستری کشف شده‌اند اما جستجوی اول سطح بین آن‌ها تمایز قائل می‌شود تا اطمینان حاصل کند که جستجو به شکل اول سطح پیش می‌رود. اگر (E (u,v و رأس u سیاه باشد آنگاه رأس v سیاه یا خاکستری است؛ به عبارت دیگر همهٔ رئوس مجاور رئوس سیاه کشف شده‌اند. رئوس خاکستری ممکن است رأس مجاور به رنگ سفید داشته باشند؛ آن‌ها مرز بین رئوس کشف شده و کشف نشده را نشان می‌دهند.

جستجوی اول سطح یک درخت اول سطح را می‌سازد، که در آغاز تنها شامل ریشه‌است که رأس منبع s می‌باشد. هر وقت رأس سفید v در مرحلهٔ پویش لیست همجواری رأس کشف شده u، کشف شود رأس v‌و یال (u,v)‌به درخت اضافه می‌شوند. می‌گوییم u ما قبل یا پدرparent) v در درخت جستجوی اول سطح است. از آن جایی که هر رأس حداکثر یک بار کشف می‌شود، حداکثر یک پدر دارد رابطهٔ جد و نتیجه (نسل) در درخت جستجوی اول سطح به شکل معمول نسبت به ریشهٔ s تعریف می‌شود: اگر u‌در مسیری از درخت از s به v واقع باشد آنگاه u جد v‌و v نتیجهٔ u است.

روال جستجوی اول سطح (BFS) زیر فرض می‌کند که گراف ورودی (G=(V,E با استفاده از لیست همجواری نمایش داده می‌شود. چندین ساختمان دادهٔ اضافی همراه هر رأس در گراف نگهداری می‌شود. رنگ هر رأس V u در متغیر color[u] و ما قبل U در متغیر ذخیره می‌شود. اگر u فاقد ماقبل باشد (برای مثال u=s یا u کشف نشده با شد) آن گاه فاصله از منبع s تا رأس u که توسط الگوریتم محاسبه می‌شود در d[u] ذخیره می‌گردد. الگوریتم همچنین از صف اولین ورودی اولین خروجیFirst in_First Out) Q برای مدیریت مجموعه رئوس خاکستری استفاده می‌کند.

برای مشاهدهٔ روند بهتری از الگوریتم به این پیوند مراجعه کنید!

۱ (Algorithm BFS(G,v)
۲  Input : G=(V,E), v(a vetex of G)
۳  Output : depends on the application
۴  begin
۵      mark v
۶      put v in the queue
۷      while the queue in not empty do
۸          remove first vertex w from the queue
۹          perform preWORK on w

۱۰ for all edge (w,x) such that x is unmarked do ۱۱ mark k ۱۲ put x in the queue ۱۳ end

نتایج جستجوی اول سطح ممکن است به ترتیب ملاقات رئوس همجواری رأس مورد نظر بستگی داشته باشد: درخت اول سطح ممکن است تغییر کند اما فاصلهٔ d محاسبه شده توسط الگوریتم تغییر نمی‌کند.

جستجوی اول عمق

مقالهٔ اصلی: الگوریتم جستجوی اول عمق

استراتژی ای که به وسیلهٔ جستجوی اول عمق دنبال می‌شود، همان طور که نامش اشاره دارد، جستجوی عمیق تر در گراف تا زمانی که ممکن است، می‌باشد. در جستجوی اول عمق(Depth_First_search) یال‌های خروجی از رأس v مرور شده باشند، جستجوبرای مرور یال‌ها ی خروجی از رأسی که از آن v کشف شده بود «بازگشت به عقب» می‌کند. این فرایند ادامه می‌یابد تا زمانی که همهٔ یال‌ها ی قابل دسترسی از مبدأ صلی s را کشف کنیم. اگر رأس‌های کشف نشده‌ای باقی بمانند، آن گاه یکی از رئوس به عنوان مبدأ جدید انتخاب می‌گردد و جستجو از آن مبدأ تکرار می‌شود. کل این فرایند تا زمانی که همهٔ رئوس کشف شوند تکرار می‌گردد.

همانند جستجوی اول سطح، هنگامی که رأس v در طی پویش لیست همجواری رأس u که قبلاً کشف شده، کشف می‌گردد جستجوی اول عمق این رویداد را با قرار دادن u در فیلد ماقبل v یعنی ثبت می‌کند. بر خلاف جستجوی اول سطح که زیر گراف ماقبل آن، یک درخت را تشکیل می‌دهد، زیرگراف ماقبل تولید شده به وسیلهٔ جستجوی اول عمق ممکن است از چندین درخت تشکیل شده باشد، چون جستجو ممکن است از چند مبدأ تکرار شود. بنابراین زیرگراف ماقبل جستجوی اول عمق اندکی متفاوت با زیرگراف ماقبل جستجوی اول سطح تعریف می‌شود: فرض می‌کنیم که زیرگراف ماقبل جستجوی اول عمق، جنگل اول عمق تشکیل شده از چندین درخت اول عمق را شکل می‌دهد. یال‌ها در، یال‌های درختی نامیده می‌شوند. همانند جستجوی اول سطح، رئوس در طی جستجو جهت مشخص شدن وضعیت شان رنگ می‌شوند. هر رأس در آغاز سفید است، وقتی در جستجو کشف می‌شود، خاکستری می‌گردد و وقتی خاتمه می‌یابد، سیاه رنگ می‌شود، به عبارت دیگر وقتی لیست همجواری آن به‌طور کامل بررسی می‌گردد. این تکنیک تضمین می‌کند که هر رأس در دقیقاً یک درخت اول عمق خاتمه می‌یابد که به موجب آن درخت‌ها متمایز هستند. علاوه بر ایجاد جنگل اول عمق، جستجوی اول عمق هر رأس را برچسب دهی زمانی نیز می‌کند. هر رأس v دارای دو برچسب زمانی می‌باشد: وقتی رأس v در ابتدا کشف می‌گردد (خاکستری می‌گردد) اولین برچسب d]v] ثبت می‌شود و دومین برچسب زمانی f[v] زمانی ثبت می‌شود که جستجو، بررسی لیست همسایگی v را خاتمه دهد (و v را سیاه رنگ کند) این برچسب‌های زمانی در بسیاری از الگوریتم‌های گراف استفاده می‌شوند و به‌طور کلی در استدلال در مورد رفتار جستجوی اول عمق مفید هستند.

روال جستجوی اول عمق(DFS) زیر، زمان کشف رأس را در متغیر d]v] و زمان خاتمهٔ رأس u را در متغیر f]u] ثبت می‌کند. این برچسب‌های زمانی اعداد صحیح بین ۱ تا ۲|V| هستند، چون برای هر یک از |V| رأس یک رویداد کشف و یک رویداد خاتمه وجود دارد. برای هر رأس u داریم: d[u] < f[u رأس u قبل از d[u]، white و بین d]u] و f[u]، Gray و بعد از f[u]، Black می‌باشد. شبه کد زیر الگوریتم اصلی جستجوی اول عمق است. گراف ورودی G ممکن است جهت دار یا بدون جهت باشد. متغیر time یک متغیر سراسری است که برای برچسب دهی زمانی استفاده می‌شود.

dfs(graph G)

{

 list L = empty
 tree T = empty
 choose a starting vertex x
 search(x)
 while(L is not empty)
 {
   remove edge (v, w) from beginning of L
   if w not yet visited
   {
     add (v, w) to T
     search(w)
   }
 }
}

search(vertex v) { visit v

 for each edge (v, w)
   add edge (v, w) to the beginning of L

}

ویژگی‌های جستجوی اول عمق

جستجوی اول عمق باعث می‌شود اطلاعات با ارزشی از ساختار گراف بدست آوریم. شاید اساسی‌ترین ویژگی جستجوی اول عمق این است که زیرگراف ما قبل به راستی یک جنگل از درخت‌ها را شکل می‌دهد، چون ساختار درخت‌ها ی اول عمق، بازتاب دهندهٔ ساختار فراخوانی بازگشتی DFS_Visit می‌باشد. به عبارت دیگر اگر و فقط اگر DFS_Visit)v) در طی جستجوی لیست همجواری u فراخوانی شده باشد، به علاوه، رأس v نتیجهٔ رأس u در جنگل اول عمق است اگر و فقط اگر v در طی زمانی که u خاکستری است کشف شود. ویژگی مهم جستجوی اول عمق این است که زمان‌های کشف و خاتمه ساختار پرانتزی دارند. اگر کشف رأس u را با پرانتز چپ«u)» و خاتمه را به وسیلهٔ پرانتز راست «(u» نشان دهیم، آن گاه کشف‌ها و خاتمه‌ها یک عبارت خوش فرم در جمله ایجاد می‌کنند که پرانتزها به‌طور صحیح تو در تو می‌باشند.

منابع

• کتاب CLRS
• http://en.wikipedia.org/wiki/Breadth-first_search
• http://en.wikipedia.org/wiki/Depth-first_search