گراف (نوع داده‌های انتزاعی)

در علوم رایانه یک گراف، داده‌ساختاری انتزاعی است که هدفش به کارگیریِ مفهوم گراف از ریاضیات است. یک داده ساختار گراف اساساً از یک مجموعهٔ متناهی ِ زوج‌های مرتب- موسوم به یال- شامل واحدهایی به نام رأس یا گره تشکیل می‌شود؛ همانطور که در ریاضیات به ازای یک یال (u,v) می‌گوییم که u به v می‌رود یا u و v مجاوراند.

نمایش گراف‌ها

به طور معمول دو راه برای نمایش یک گراف (G=(V,E وجود دارد: به صورت مجموعه‌ای از لیست‌های مجاورت یا به صورت یک ماتریس مجاورت. هر دو راه قابل اجرا برای گراف‌های جهت‌دار و بدون جهت است. نمایش لیست مجاورت معمولاً ترجیح داده می‌شود چرا که یک روش فشرده برای نمایش گراف‌های کم یال فراهم می‌کند.اگرگراف متراکم یا همان پر یال باشد، نمایشِ ماتریس مجاورت مقدم است. همچنین در مواقعی که نیاز داریم سریعاً بدانیم که آیا به ازای دو رأس داده شده یال متصل کنندهٔ بینشان وجود دارد یا خیر، از لیست مجاورت استفاده می‌کنیم.

الگوریتم‌های گراف

الگوریتم‌های گراف زمینهٔ مهم علاقه در علوم رایانه به حساب می‌آیند. برخی از عملیاتِ مربوط به گراف‌ها عبارتند از: پیدا کردن مسیری بین دو گره، مانند جستجوی عمق اول و جستجوی سطح اول و پیدا کردن کوتاهترین مسیر از یک گره به دیگری، مانند الگوریتم دیکسترا. یک روش برای پیدا کردن کوتاهترین مسیر بین هر گره و تمام گره‌های دیگر هم وجود دارد به نام الگوریتم فلوید-وارشال.

منابع

• توماس اچ کورمن, Charles E. Leiserson, Ronald L. Rivest, and کلیفورد استین. “26”. In مقدمه‌ای بر الگوریتم‌ها. 2nd edition ed. MIT Press and McGraw-Hill, 2001. 696–697. ISBN 0-262-03293-7.