23-12-2024, 06:33 PM
نمایش گراف با استفاده از لیست پیوندی
بتوانیم به راحتی به آنها دسترسی داشته باشیم. لیست پیوندی یکی از روشهای کارآمد برای نمایش گراف است، مخصوصاًاًوقتی میخواهیم یک گراف را نمایش دهیم، هدف این است که اطلاعات مربوط به راسها و یالها را به نحوی ذخیره کنیم که
.زمانی که تعداد یالها کمتر از تعداد تمام ترکیبهای ممکن بین راسها باشد (گراف خلوت یا کمتراکم)
در روش لیست پیوندی، به جای استفاده از ماتریس (که بیشتر حافظه رو مصرف میکنه)، برای هر راس یک لیست داریم که
راسهای متصل به اون رو ذخیره میکنه.این لیست نشان دهنده همسایگان گره است، که این لیست معمولا با استفاده از یک آرایه
.یا ساختار های دیگر پیاده سازی می شود
ساختار داده در این روش
ً هر راس یک لیست داره: مثلا راس (A) لیستی داره که تمام راسهای متصل به اون رو در خودش داره.
هر عنصر لیست شامل یک اشارهگر به راس متصلشده است: به این ترتیب، برای هر یال، اشارهگری به راس مقصد
.داریم
مثالی از یک گراف و نمایش لیست پیوندی آن
:فرض کنید گراف زیر رو داریم
راس A به B و C وصله.
راس B به C و D وصله.
راس C فقط به D وصله.
:لیست پیوندی برای این گراف به این صورت نمایش داده میشه
A: → B → C
B: → C → D
C: → D
)هیچ ارتباطی نداره(
چند نکته
.در این روش ، هر راس به یک لیست از گره های مجاورش اشاره می کند
.اگر گراف بدون جهت باشد ،هر یال در هر دو راس ذخیره می شود
.برای گراف های وزنی ، وزن ها نیز همراه با راس ها ذخیره می شوند
مزایای استفاده از لیست پیوندی
صرفهجویی در فضا: در گرافهای خلوت که تعداد یالها کم است، لیست پیوندی فقط یالهای موجود را ذخیره میکند و فضای
.اضافی برای یالهای غیرفعال (که وجود ندارند) اشغال نمیکند
افزودن و حذف یالها: اضافه یا حذف کردن یک یال در لیست پیوندی سادهتر است. کافی است یال موردنظر را به لیست پیوندی
.راس مربوطه اضافه یا از آن حذف کنیم
پیچیدگی زمانی
در لیست پیوندی برای هر راس، یک لیست از همسایههایش ذخیره میشود. برای بررسی همسایهها، باید در لیست هر راس به ترتیب
.بررسی کنیم
زمان پیچیدگی بستگی به تعداد همسایهها دارد
اگر یک راس، d همسایه داشته باشد، زمان پیچیدگی )O)d است که در آن d درجه راس (تعداد یالهای خروجی) است.
برای بررسی وجود یال بین دو راس، باید لیست همسایهها را جستجو کرد. بنابراین در بدترین حالت، زمان پیچیدگی برای جستجوی
یال بین دو راس )O)d است
پیچیدگی حافظه پیچیدگی حافظه
در لیست پیوندی برای هر راس، لیستی از همسایهها را ذخیره میکنیم. اگر E تعداد یالها باشد، چون هر یال در یک گراف بدون
جهت در دو لیست همسایگی ذخیره میشود، حافظه مورد نیاز برابر با )O)V + E است.
در لیست پیوندی برای هر راس، لیستی از همسایهها را ذخیره میکنیم. اگر E تعداد یالها باشد، چون هر یال در یک گراف بدون
جهت در دو لیست همسایگی ذخیره میشود، حافظه مورد نیاز برابر با )O)V + E است.
در گرافهای کمدرجه (گرافهایی با تعداد یال کم)، لیست پیوندی به مراتب حافظه کمتری نسبت به ماتریس مجاورت نیاز دارد. در گرافهای کمدرجه (گرافهایی با تعداد یال کم)، لیست پیوندی به مراتب حافظه کمتری نسبت به ماتریس مجاورت نیاز دارد.
نتیجهگیری: نتیجهگیری:
اگر گراف متراکم است (تعداد یالها زیاد است)، استفاده از ماتریس مجاورت ممکن است مفیدتر باشد چون دسترسی سریعتری به
یالها خواهید داشت، حتی اگر حافظه بیشتری مصرف کند.
اگر گراف متراکم است (تعداد یالها زیاد است)، استفاده از ماتریس مجاورت ممکن است مفیدتر باشد چون دسترسی سریعتری به
یالها خواهید داشت، حتی اگر حافظه بیشتری مصرف کند.
ًبهتر است، چون حافظه کمتری مصرف میکند و
اگر گراف کمدرجه است (تعداد یالها کم است)، استفاده از لیست پیوندی معمولا
پیچیدگی زمانی برای پیدا کردن همسایهها بهطور میانگین کمتر خواهد بود.
پیمایش گراف پیمایش گراف
پیمایش گراف به این معنیه که ما میخواهیم همه راسها و یالهای گراف رو بازدید کنیم تا به اطلاعات مختلفی از ساختار گراف دسترسی پیدا
کنیم. اهداف پیمایش گراف میتونند شامل موارد زیر باشند:
پیمایش گراف به این معنیه که ما میخواهیم همه راسها و یالهای گراف رو بازدید کنیم تا به اطلاعات مختلفی از ساختار گراف دسترسی پیدا
کنیم. اهداف پیمایش گراف میتونند شامل موارد زیر باشند:
یافتن مسیرها یا اتصالها: بررسی اینکه آیا مسیری بین دو راس وجود داره یا نه. یافتن مسیرها یا اتصالها: بررسی اینکه آیا مسیری بین دو راس وجود داره یا نه.
ًپیدا کردن اینکه گراف همبند هست یا نه (همه راسها به هم متصلاند یا نه).
ًپیدا کردن اینکه گراف همبند هست یا نه (همه راسها به هم متصلاند یا نه). بررسی ویژگیهای گراف: مثلا
بررسی ویژگیهای گراف: مثلا
پیدا کردن کوتاهترین یا بهترین مسیر: این مورد در کاربردهای عملی مثل شبکههای ارتباطی و نقشهها خیلی مهمه. پیدا کردن کوتاهترین یا بهترین مسیر: این مورد در کاربردهای عملی مثل شبکههای ارتباطی و نقشهها خیلی مهمه.
تفاوت پیمایش گراف و پیمایش درخت تفاوت پیمایش گراف و پیمایش درخت
پیمایش گراف و درخت از نظر اصول کلی شبیه به هم هستند، اما تفاوتهای مهمی دارند: پیمایش گراف و درخت از نظر اصول کلی شبیه به هم هستند، اما تفاوتهای مهمی دارند:
وجود حلقه (سیکل): گراف ممکن است حلقه داشته باشد، اما درخت هیچ حلقهای ندارد. بنابراین در پیمایش گراف، باید مراقب حلقهها باشیم تا به
راسهای بازدیدشده دوباره برنگردیم، ولی در پیمایش درخت نیازی به این کار نیست.
وجود حلقه (سیکل): گراف ممکن است حلقه داشته باشد، اما درخت هیچ حلقهای ندارد. بنابراین در پیمایش گراف، باید مراقب حلقهها باشیم تا به
راسهای بازدیدشده دوباره برنگردیم، ولی در پیمایش درخت نیازی به این کار نیست.
همبندی و تعداد مسیرها: درخت همیشه همبند است و فقط یک مسیر منحصربهفرد بین هر دو راس وجود دارد. اما گراف ممکن است همبند نباشد و
بیش از یک مسیر بین دو راس داشته باشد.
همبندی و تعداد مسیرها: درخت همیشه همبند است و فقط یک مسیر منحصربهفرد بین هر دو راس وجود دارد. اما گراف ممکن است همبند نباشد و
بیش از یک مسیر بین دو راس داشته باشد.
راس ریشه: درخت یک راس ریشه دارد که پیمایش از آن آغاز میشود و به کل درخت دسترسی داریم. اما در گراف راس شروع دلخواه است و ممکن
است کل گراف از آن دسترسیپذیر نباشد (در گرافهای ناهمبند).
راس ریشه: درخت یک راس ریشه دارد که پیمایش از آن آغاز میشود و به کل درخت دسترسی داریم. اما در گراف راس شروع دلخواه است و ممکن
است کل گراف از آن دسترسیپذیر نباشد (در گرافهای ناهمبند).
به طور خلاصه، پیمایش درخت سادهتر و مستقیمتر از پیمایش گراف است، چون در درخت نیازی به بررسی حلقهها یا مسیرهای متعدد نیست
الگوریتم کلی برای پیمایش گراف
در پیمایش گراف، الگوریتم کلی به این صورت عمل میکنه:
ً انتخاب یک راس شروع: پیمایش گراف از یک راس دلخواه، که معمولا راس "شروع" نامیده میشه، آغاز میشه.
علامتگذاری یا ثبت بازدید شده: وقتی به یک راس رسیدیم، اون راس رو به عنوان "بازدید شده" علامتگذاری میکنیم، تا از بازدید
دوباره همون راس جلوگیری کنیم.
بازدید از همسایهها: به سراغ همسایههای مستقیم راس میریم و هر کدوم رو بازدید و علامتگذاری میکنیم.
تکرار بازدید برای همسایهها: به ترتیب از همسایههای همسایهها بازدید میکنیم، تا وقتی که همه راسهای قابل دسترسی از راس شروع
بازدید بشن.
ً بازگشت و ادامه از راسهای بعدی: اگر گراف دارای چندین قسمت جدا باشه (مثلا چندین زیرگراف بدون ارتباط)، الگوریتم به سراغ
راسهای باقیمانده که هنوز بازدید نشدهاند میره.
در واقع این الگوریتم سعی میکنه تا از هر راس به تمامی نقاط متصل به اون دسترسی پیدا کنه و این کار رو تا جایی ادامه میده که همه
نقاط ممکن بازدید بشن
پیاده سازی کلی پیمایش گراف
پیمایش گراف می تونه با لیست مجاورت یا ماتریس مجاورت انجام بشه
در روش لیست مجاورت ،هر راس یک لیست از همسایه های خود دارد که با یال به آن متصل -1
.اند ،و پیمایش با مراجعه به این لیست ها انجام می شود
2-در روش ماتریس مجاورت ، یک ماتریس v*v داریم که نشان می ده هر جفت راس آیا به هم
متصل اند یا نه . این ماتریس برای پیمایش استفاده می شه تا بفهمیم از یک راس به کدام راس
ها می تونیم حرکت کنیم
یک الگوریتم پیمایش گراف باید ویژگیهای زیر را داشته باشد تا بتواند کارایی و
:دقت لازم را فراهم کند
کامل بودن: الگوریتم باید تضمین کند که تمام راسها و یالهای موجود در گراف را بازدید میکند، تا هیچ بخشی از گراف از قلم نیفتد. این ویژگی
مخصوصاًاًدر گرافهای همبند اهمیت دارد که همه نقاط از راس شروع قابل دسترسیاند.
پرهیز از حلقه بینهایت: در گرافهای جهتدار یا بدون جهت که ممکن است حلقه (سیکل) داشته باشند، الگوریتم باید از بازگشت به راسهای
ًبازدیدشده جلوگیری کند، تا در حلقه بینهایت گرفتار نشود. برای این کار معمولا از یک لیست یا مجموعه از راسهای بازدیدشده استفاده میشود.
بهینهسازی زمان و فضا: الگوریتم پیمایش باید از لحاظ زمانی و فضایی کارآمد باشد، بهویژه برای گرافهای بزرگ. برای این منظور، ساختار
دادههای مناسبی مانند پشته (برای DFS) و صف (برای BFS) به کار میروند.
قابلیت پیادهسازی با ساختار دادههای مختلف: الگوریتم باید طوری طراحی شود که بتواند روی انواع ساختارهای ذخیرهسازی گراف (مثل
لیست مجاورت و ماتریس مجاورت) پیادهسازی شود.
یافتن مسیرها یا تعیین توالیها: الگوریتم باید بتواند اطلاعاتی درباره توالی بازدیدها یا مسیر بین راسها را ذخیره کند. این ویژگی به
خصوص برای حل مسائلی مثل پیدا کردن کوتاهترین مسیر، شناسایی مؤلفههای همبند و یافتن ترتیبهای خاص مفید است.
قابلیت استفاده در گرافهای وزندار و بدون وزن: الگوریتم باید طوری طراحی شود که هم در گرافهای وزندار و هم در گرافهای بدون وزن
قابل استفاده باشد. در گرافهای وزندار، ممکن است نیاز به تغییراتی در الگوریتم (مثل استفاده از الگوریتمهای دیگر برای کوتاهترین مسیر) باشد
پیمایش گراف یک فرآیند اساسیه که با الگوریتم سادهای انجام میشه. این الگوریتم به ترتیب همه نقاط متصل به هم رو پیدا و بازدید میکنه تا به
اطلاعات مختلفی در مورد ساختار و ویژگیهای گراف دسترسی داشته باشیم
بتوانیم به راحتی به آنها دسترسی داشته باشیم. لیست پیوندی یکی از روشهای کارآمد برای نمایش گراف است، مخصوصاًاًوقتی میخواهیم یک گراف را نمایش دهیم، هدف این است که اطلاعات مربوط به راسها و یالها را به نحوی ذخیره کنیم که
.زمانی که تعداد یالها کمتر از تعداد تمام ترکیبهای ممکن بین راسها باشد (گراف خلوت یا کمتراکم)
در روش لیست پیوندی، به جای استفاده از ماتریس (که بیشتر حافظه رو مصرف میکنه)، برای هر راس یک لیست داریم که
راسهای متصل به اون رو ذخیره میکنه.این لیست نشان دهنده همسایگان گره است، که این لیست معمولا با استفاده از یک آرایه
.یا ساختار های دیگر پیاده سازی می شود
ساختار داده در این روش
ً هر راس یک لیست داره: مثلا راس (A) لیستی داره که تمام راسهای متصل به اون رو در خودش داره.
هر عنصر لیست شامل یک اشارهگر به راس متصلشده است: به این ترتیب، برای هر یال، اشارهگری به راس مقصد
.داریم
مثالی از یک گراف و نمایش لیست پیوندی آن
:فرض کنید گراف زیر رو داریم
راس A به B و C وصله.
راس B به C و D وصله.
راس C فقط به D وصله.
:لیست پیوندی برای این گراف به این صورت نمایش داده میشه
A: → B → C
B: → C → D
C: → D
)هیچ ارتباطی نداره(
چند نکته
.در این روش ، هر راس به یک لیست از گره های مجاورش اشاره می کند
.اگر گراف بدون جهت باشد ،هر یال در هر دو راس ذخیره می شود
.برای گراف های وزنی ، وزن ها نیز همراه با راس ها ذخیره می شوند
مزایای استفاده از لیست پیوندی
صرفهجویی در فضا: در گرافهای خلوت که تعداد یالها کم است، لیست پیوندی فقط یالهای موجود را ذخیره میکند و فضای
.اضافی برای یالهای غیرفعال (که وجود ندارند) اشغال نمیکند
افزودن و حذف یالها: اضافه یا حذف کردن یک یال در لیست پیوندی سادهتر است. کافی است یال موردنظر را به لیست پیوندی
.راس مربوطه اضافه یا از آن حذف کنیم
پیچیدگی زمانی
در لیست پیوندی برای هر راس، یک لیست از همسایههایش ذخیره میشود. برای بررسی همسایهها، باید در لیست هر راس به ترتیب
.بررسی کنیم
زمان پیچیدگی بستگی به تعداد همسایهها دارد
اگر یک راس، d همسایه داشته باشد، زمان پیچیدگی )O)d است که در آن d درجه راس (تعداد یالهای خروجی) است.
برای بررسی وجود یال بین دو راس، باید لیست همسایهها را جستجو کرد. بنابراین در بدترین حالت، زمان پیچیدگی برای جستجوی
یال بین دو راس )O)d است
پیچیدگی حافظه پیچیدگی حافظه
در لیست پیوندی برای هر راس، لیستی از همسایهها را ذخیره میکنیم. اگر E تعداد یالها باشد، چون هر یال در یک گراف بدون
جهت در دو لیست همسایگی ذخیره میشود، حافظه مورد نیاز برابر با )O)V + E است.
در لیست پیوندی برای هر راس، لیستی از همسایهها را ذخیره میکنیم. اگر E تعداد یالها باشد، چون هر یال در یک گراف بدون
جهت در دو لیست همسایگی ذخیره میشود، حافظه مورد نیاز برابر با )O)V + E است.
در گرافهای کمدرجه (گرافهایی با تعداد یال کم)، لیست پیوندی به مراتب حافظه کمتری نسبت به ماتریس مجاورت نیاز دارد. در گرافهای کمدرجه (گرافهایی با تعداد یال کم)، لیست پیوندی به مراتب حافظه کمتری نسبت به ماتریس مجاورت نیاز دارد.
نتیجهگیری: نتیجهگیری:
اگر گراف متراکم است (تعداد یالها زیاد است)، استفاده از ماتریس مجاورت ممکن است مفیدتر باشد چون دسترسی سریعتری به
یالها خواهید داشت، حتی اگر حافظه بیشتری مصرف کند.
اگر گراف متراکم است (تعداد یالها زیاد است)، استفاده از ماتریس مجاورت ممکن است مفیدتر باشد چون دسترسی سریعتری به
یالها خواهید داشت، حتی اگر حافظه بیشتری مصرف کند.
ًبهتر است، چون حافظه کمتری مصرف میکند و
اگر گراف کمدرجه است (تعداد یالها کم است)، استفاده از لیست پیوندی معمولا
پیچیدگی زمانی برای پیدا کردن همسایهها بهطور میانگین کمتر خواهد بود.
پیمایش گراف پیمایش گراف
پیمایش گراف به این معنیه که ما میخواهیم همه راسها و یالهای گراف رو بازدید کنیم تا به اطلاعات مختلفی از ساختار گراف دسترسی پیدا
کنیم. اهداف پیمایش گراف میتونند شامل موارد زیر باشند:
پیمایش گراف به این معنیه که ما میخواهیم همه راسها و یالهای گراف رو بازدید کنیم تا به اطلاعات مختلفی از ساختار گراف دسترسی پیدا
کنیم. اهداف پیمایش گراف میتونند شامل موارد زیر باشند:
یافتن مسیرها یا اتصالها: بررسی اینکه آیا مسیری بین دو راس وجود داره یا نه. یافتن مسیرها یا اتصالها: بررسی اینکه آیا مسیری بین دو راس وجود داره یا نه.
ًپیدا کردن اینکه گراف همبند هست یا نه (همه راسها به هم متصلاند یا نه).
ًپیدا کردن اینکه گراف همبند هست یا نه (همه راسها به هم متصلاند یا نه). بررسی ویژگیهای گراف: مثلا
بررسی ویژگیهای گراف: مثلا
پیدا کردن کوتاهترین یا بهترین مسیر: این مورد در کاربردهای عملی مثل شبکههای ارتباطی و نقشهها خیلی مهمه. پیدا کردن کوتاهترین یا بهترین مسیر: این مورد در کاربردهای عملی مثل شبکههای ارتباطی و نقشهها خیلی مهمه.
تفاوت پیمایش گراف و پیمایش درخت تفاوت پیمایش گراف و پیمایش درخت
پیمایش گراف و درخت از نظر اصول کلی شبیه به هم هستند، اما تفاوتهای مهمی دارند: پیمایش گراف و درخت از نظر اصول کلی شبیه به هم هستند، اما تفاوتهای مهمی دارند:
وجود حلقه (سیکل): گراف ممکن است حلقه داشته باشد، اما درخت هیچ حلقهای ندارد. بنابراین در پیمایش گراف، باید مراقب حلقهها باشیم تا به
راسهای بازدیدشده دوباره برنگردیم، ولی در پیمایش درخت نیازی به این کار نیست.
وجود حلقه (سیکل): گراف ممکن است حلقه داشته باشد، اما درخت هیچ حلقهای ندارد. بنابراین در پیمایش گراف، باید مراقب حلقهها باشیم تا به
راسهای بازدیدشده دوباره برنگردیم، ولی در پیمایش درخت نیازی به این کار نیست.
همبندی و تعداد مسیرها: درخت همیشه همبند است و فقط یک مسیر منحصربهفرد بین هر دو راس وجود دارد. اما گراف ممکن است همبند نباشد و
بیش از یک مسیر بین دو راس داشته باشد.
همبندی و تعداد مسیرها: درخت همیشه همبند است و فقط یک مسیر منحصربهفرد بین هر دو راس وجود دارد. اما گراف ممکن است همبند نباشد و
بیش از یک مسیر بین دو راس داشته باشد.
راس ریشه: درخت یک راس ریشه دارد که پیمایش از آن آغاز میشود و به کل درخت دسترسی داریم. اما در گراف راس شروع دلخواه است و ممکن
است کل گراف از آن دسترسیپذیر نباشد (در گرافهای ناهمبند).
راس ریشه: درخت یک راس ریشه دارد که پیمایش از آن آغاز میشود و به کل درخت دسترسی داریم. اما در گراف راس شروع دلخواه است و ممکن
است کل گراف از آن دسترسیپذیر نباشد (در گرافهای ناهمبند).
به طور خلاصه، پیمایش درخت سادهتر و مستقیمتر از پیمایش گراف است، چون در درخت نیازی به بررسی حلقهها یا مسیرهای متعدد نیست
الگوریتم کلی برای پیمایش گراف
در پیمایش گراف، الگوریتم کلی به این صورت عمل میکنه:
ً انتخاب یک راس شروع: پیمایش گراف از یک راس دلخواه، که معمولا راس "شروع" نامیده میشه، آغاز میشه.
علامتگذاری یا ثبت بازدید شده: وقتی به یک راس رسیدیم، اون راس رو به عنوان "بازدید شده" علامتگذاری میکنیم، تا از بازدید
دوباره همون راس جلوگیری کنیم.
بازدید از همسایهها: به سراغ همسایههای مستقیم راس میریم و هر کدوم رو بازدید و علامتگذاری میکنیم.
تکرار بازدید برای همسایهها: به ترتیب از همسایههای همسایهها بازدید میکنیم، تا وقتی که همه راسهای قابل دسترسی از راس شروع
بازدید بشن.
ً بازگشت و ادامه از راسهای بعدی: اگر گراف دارای چندین قسمت جدا باشه (مثلا چندین زیرگراف بدون ارتباط)، الگوریتم به سراغ
راسهای باقیمانده که هنوز بازدید نشدهاند میره.
در واقع این الگوریتم سعی میکنه تا از هر راس به تمامی نقاط متصل به اون دسترسی پیدا کنه و این کار رو تا جایی ادامه میده که همه
نقاط ممکن بازدید بشن
پیاده سازی کلی پیمایش گراف
پیمایش گراف می تونه با لیست مجاورت یا ماتریس مجاورت انجام بشه
در روش لیست مجاورت ،هر راس یک لیست از همسایه های خود دارد که با یال به آن متصل -1
.اند ،و پیمایش با مراجعه به این لیست ها انجام می شود
2-در روش ماتریس مجاورت ، یک ماتریس v*v داریم که نشان می ده هر جفت راس آیا به هم
متصل اند یا نه . این ماتریس برای پیمایش استفاده می شه تا بفهمیم از یک راس به کدام راس
ها می تونیم حرکت کنیم
یک الگوریتم پیمایش گراف باید ویژگیهای زیر را داشته باشد تا بتواند کارایی و
:دقت لازم را فراهم کند
کامل بودن: الگوریتم باید تضمین کند که تمام راسها و یالهای موجود در گراف را بازدید میکند، تا هیچ بخشی از گراف از قلم نیفتد. این ویژگی
مخصوصاًاًدر گرافهای همبند اهمیت دارد که همه نقاط از راس شروع قابل دسترسیاند.
پرهیز از حلقه بینهایت: در گرافهای جهتدار یا بدون جهت که ممکن است حلقه (سیکل) داشته باشند، الگوریتم باید از بازگشت به راسهای
ًبازدیدشده جلوگیری کند، تا در حلقه بینهایت گرفتار نشود. برای این کار معمولا از یک لیست یا مجموعه از راسهای بازدیدشده استفاده میشود.
بهینهسازی زمان و فضا: الگوریتم پیمایش باید از لحاظ زمانی و فضایی کارآمد باشد، بهویژه برای گرافهای بزرگ. برای این منظور، ساختار
دادههای مناسبی مانند پشته (برای DFS) و صف (برای BFS) به کار میروند.
قابلیت پیادهسازی با ساختار دادههای مختلف: الگوریتم باید طوری طراحی شود که بتواند روی انواع ساختارهای ذخیرهسازی گراف (مثل
لیست مجاورت و ماتریس مجاورت) پیادهسازی شود.
یافتن مسیرها یا تعیین توالیها: الگوریتم باید بتواند اطلاعاتی درباره توالی بازدیدها یا مسیر بین راسها را ذخیره کند. این ویژگی به
خصوص برای حل مسائلی مثل پیدا کردن کوتاهترین مسیر، شناسایی مؤلفههای همبند و یافتن ترتیبهای خاص مفید است.
قابلیت استفاده در گرافهای وزندار و بدون وزن: الگوریتم باید طوری طراحی شود که هم در گرافهای وزندار و هم در گرافهای بدون وزن
قابل استفاده باشد. در گرافهای وزندار، ممکن است نیاز به تغییراتی در الگوریتم (مثل استفاده از الگوریتمهای دیگر برای کوتاهترین مسیر) باشد
پیمایش گراف یک فرآیند اساسیه که با الگوریتم سادهای انجام میشه. این الگوریتم به ترتیب همه نقاط متصل به هم رو پیدا و بازدید میکنه تا به
اطلاعات مختلفی در مورد ساختار و ویژگیهای گراف دسترسی داشته باشیم