پیمایش گراف (Graph traversal) در حالت کلی به معنی گذشتن و دیدن تمام راس‌های گراف است و معمولا پیمایش از طریق یال‌های موجود در گراف انجام می‌شود. معمولا پیمایش گراف به تنهایی ارزش خاصی ندارد و هدف از پیمایش، محاسبه یا پیدا کردن چیز دیگری است. برای مثال شاید با نگاه کردن به یک گراف بتوانید خواص آن را پیدا کنید و مسئله را حل کنید؛ اما در کامپیوتر به دلیل محدودیت‌هابه همین راحتی نمی‌توان این کار را کرد. الگوریتم‌های پیمایش در حرکت روی گراف و پیدا کردن خواص آن به ما کمک می‌کنند.

در درخت‌ها و گراف‌های بی‌دور معمولا این مشکل وجود ندارد، چرا‌که مسیر تکراری نداریم و نیازی به چک کردن رأس یا یال تکراری نیست.

هنگامی که گراف دور دارد، برای جلوگیری از رفتن مسیر‌های تکراری و نیافتادن در دام دور، نیاز به علامت‌گذاری و رنگ کردن رأس‌ها یا یال‌ها داریم. بنابراین هر‌گاه وارد رأس یا یالی شدیم آن را علامت می‌زنیم تا دفعه بعدی که وارد آن شدیم بتوانیم بفهمیم که قبلا هم اینجا بوده‌ایم یا نه؛ سپس با توجه به این نکته می‌توانیم بفهمیم که ادامه پیمایش از این رأس یا یال را ادامه دهیم یا آن را همین گونه رها کنیم.

معمولا در بدنه‌ی الگوریتم‌ها از این مطلب به اسم رأس دیده شده (visited) یا علامت زده شده (marked) یاد می‌شود و لیست یا آرایه‌ای برای نگه‌داری علامت‌ها اختصاص می‌دهند.

الگوریتم های گوناگونی برای پیمایش گراف وجود دارد؛ اما دو الگوریتم بسیار معروف برای اینکار وجود دارد، یکی جست‌وجوی عمق‌اول و دیگری جست‌و‌جوی سطح‌اول. هر دو الگوریتم روی تمام گراف‌ها از جمله گراف های چندگانه و جهت‌دار نیز کارا هستند. تفاوت مهم این دو معمولا در این است که عمق‌اول عمدتا برای کارهای بازگشتی و سطح‌اول عمدتا برای پیدا کردن کوتاه‌ترین مسیر استفاده می‌شود.

• تست دو بخشی بودن گراف
• شناسایی مرکز گراف
• شناسایی کمر گراف
• شناسایی قطر گراف
• پیدا کردن مؤلفه‌‌های همبند

• ویکی‌پدیا