پیمایش گراف

پیمایش گراف به معنی بازدید از تک‌تک راس‌های گراف به نحوی خاص است. مسئله پیمایش درخت حالت خاصی از پیمایش گراف است. برای این کار الگوریتم‌هایی چند هست.
جستجوی اول سطح
جست و جوی اول سطح (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 در متغیر coloru و ما قبل U در متغیر ذخیره می‌شود. اگر u فاقد ماقبل باشد (برای مثال u=s یا u کشف نشده با شد) آن گاه فاصله از منبع s تا راس u که توسط الگوریتم محاسبه می‌شود در du ذخیره می‌گردد. الگوریتم همچنین از صف اولین ورودی اولین خروجی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 در ابتدا کشف می‌گردد (خاکستری می‌گردد) اولین برچسب dv ثبت می‌شود و دومین برچسب زمانی fv زمانی ثبت می‌شود که جستجو، بررسی لیست همسایگی v را خاتمه دهد (و v را سیاه رنگ کند) این برچسب‌های زمانی در بسیاری از الگوریتم‌های گراف استفاده می‌شوند و به طور کلی در استدلال در مورد رفتار جستجوی اول عمق مفید هستند.
روال جستجوی اول عمق(DFS) زیر، زمان کشف راس را در متغیر dv و زمان خاتمه راس u را در متغیر fu ثبت می‌کند. این برچسب‌های زمانی اعداد صحیح بین ۱ تا ۲|V| هستند، چون برای هر یک از |V| راس یک رویداد کشف و یک رویداد خاتمه وجود دارد.برای هر راس u داریم: du < fu
راس u قبل از du، white و بین du و fu، Gray و بعد از fu، 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» نشان دهیم، آن گاه کشف‌ها و خاتمه‌ها یک عبارت خوش فرم در جمله ایجاد می‌کنند که پرانتزها به طور صحیح تو در تو می‌باشند.