http://forum.kishtech.ir/ Fri, 10 Apr 2026 12:31:18 +0000 MyBB http://forum.kishtech.ir/showthread.php?tid=111291 Mon, 23 Dec 2024 18:37:01 +0330 amirhossein shirazi]]> http://forum.kishtech.ir/showthread.php?tid=111291

---

نمونه سوال گراف

  امیرحسین شیرازی بخش اول گراف.pdf (اندازه: 699.86 KB / تعداد دفعات دریافت: 0)

  نمونه سوال بخش اول گراف.pdf (اندازه: 70.89 KB / تعداد دفعات دریافت: 0) ]]>

---

نمونه سوال گراف

  امیرحسین شیرازی بخش اول گراف.pdf (اندازه: 699.86 KB / تعداد دفعات دریافت: 0)

  نمونه سوال بخش اول گراف.pdf (اندازه: 70.89 KB / تعداد دفعات دریافت: 0) ]]> http://forum.kishtech.ir/showthread.php?tid=111285 Mon, 23 Dec 2024 17:53:17 +0330 amirhossein shirazi]]> http://forum.kishtech.ir/showthread.php?tid=111285 رأس ها نشان دهنده اشیاء یا عناصر هستند و یال ها نشان دهنده روابط بین این عناصر هستند.
تعریف گراف :هر گراف را به صورت )G = )V,Eکه از مجموعه ناتهی از رأس ها )V)Vertex و مجموعه ای از یال های )E)Edge تشکیل شده است.
انواع گراف
جهت دار :
ترتیب گره ها در زوج مرتب اهمیت دارد.
2-غیرجهت دار :
گرافی است که درآن جای دو رأس در مجموعه یالها اهمیت نداشته باشد.

گراف پوچ :گرافی است که مجموعه یال های آن تهی باشد به عبارت دیگر یعنی فقط رأس ها در آن وجود دارند.
گره مجاور: گره X مجاور گره Y است اگر بین آنها یک یال وجود داشته باشد .
راس منفرد (منزوی) : رأسی که هیچ رأس مجاوری نداشته باشد.
طوقه (Loop ) : یالی که گره ابتدا و انتها آن یکی باشد.
گراف چندگانه (Multi Graph) : گرافی است که در آن داشتن یال های چندگانه و طوقه مجاز باشد.

گراف برچسب دار: گرافی است اطلاعاتی به یال های آن نسبت داده شده است.
گراف وزن دار : گرافی است که به هر یال آن یک مقدار عددی غیر منفی نسبت داده شده است.
گراف کامل (complete Graph) :گرافی است که بین هر دو رأس آنیک یال وجود دارد به عبارتی گرافی است که حداکثر تعداد یال
ها را دارد.

درجه گره : درجه گره برابر است با مجموع تعداد یال های متصل به یک گره .
درجه گراف : برابر است با بزرگترین درجه گره های گراف .
درجه ورودی : به تعداد یال های وارد شده به یک رأس در یک گراف جهت دار درجه ورودی آن رأس می گویند.
درجه خروجی : به تعداد یال های خارج شده از یک رأس در یک گراف جهت دار درجه خروجی آن رأس می گویند.
مسیر: مجموعه ای از یال های پشت سر هم که دو رأس را به هم وصل می کنند.
مسیر ساده : مسیری است که همه رأس های آن مجزا باشد به جز اولی و آخری .
طول مسیر : تعداد یال های موجود در مسیر است.
حلقه یا سیکل : مسیر ساده ای که گره اول و آخر آن یکی باشد.

گره چاه : گره ای که درجه خروجی صفر و درجه ورودی
مثبت داشته باشد را گره چاه می گوییم.
گره منبع : گره ای که درجه خروجی مثبت و درجه ورودی
صفر داشته باشد را گره منبع می گوییم.
گراف همبند و غیر همبند :
گراف همبند: یک گراف همبند گرافی است که درآن از هر
رأس می توان به تمام رأس های دیگراز طریق یال ها رسید .
به عبارت دیگر برای هر دو رأس دلخواه در گراف یک مسیر
از یال ها وجود دارد که این دو رأس را به هم وصل کند .
گراف ناهمبند : در گراف ناهمبند ممکن است بعضی رأس ها
به یکدیگر متصل نباشند به عبارت دیگر برای بعضی رأس ها
هیچ مسیری برای رسیدن به دیگر رأس ها وجود ندارد و
گراف به چند بخش مجزا تقسیم شود.

گراف جهت دار همبند قوی و ضعیف :
گراف همبند قوی جهت دار : در این نوع گراف بین هر جفت از رأس ها مسیر های جهت دار به طور کامل در هر دو جهت وجود دارند.یعنی اگر از یک رأس
شروع کنیم می توانیم به راس های دیگر برسیم.
گراف همبند ضعیف جهت دار: به گرافی گفته می شود که در آن جهت یال ها نادید گرفته شود به عبارت دیگر در این گراف هیچ گونه مسیری از یک رأس به
رأس های دیگر وجود نداشته باشد.
تفاوت درخت با گراف
1- درخت یک گراف بدون حلقه است که یک گره خاص بنام ریشه دارد و از ریشه ی درخت یک مسیر ساده به گره های دیگر وجود دارد. پس میتوان گفت که
درخت یک گراف متصل است.
2- پیمایش درخت از ریشه به گرههای دیگر صورت میپذیرد. پس میتوان گفتن ه درخت یک گراف جهت دار است .

ما به دو روش می توانیم گراف را نمایش دهیم :
1- ماتریس مجاورت 2- لیست مجاورت
1 – ماتریس مجاورت : ماتریس مجاورت یا همجواری یک گراف با n رأس آرایه ای n × n است که به صورت زیر تعریف می شود .
نکته1: ماتریس مجاورتی یک گراف بدون جهت حتما متقارن است و
می توان برای نگهداری آن از ماتریس بالا یا پایین مثلثی استفاده کرد.
نکته2:ماتریس مجاورت یا همجواری گراف جهت دار لزوما متقارن نیست.
نکته3: در ماتریس مجاورتی برای گراف جهت دار مجموع سطری درجه خروجی و مجموع ستونی درجه ورودی رأس نظیر یاسطر یا
ستون را نشان می دهد ولی برای گراف بدون جهت مجموع سطری یا ستونی درجه هر رأس نظیر است.
نکته 4:تعداد « 1» ها در ماتریس مجاورتی گراف بدون جهت دو برابر یال ها و در گراف جهت دار برابر با یال ها است .
نکته5: از نقاط قوت ماتریس مجاورتی می توان به سرعت دسترسی به مجاور بودن یا نبودن دو گره اشاره کرد که با زمان )O)1انجام
می شود.
نکته 6:با استفاده از ماتریس مجاورتی همه الگوریتم های لازم برای گراف با n رأس با زمان )O)n² انجام می شود

لیست مجاورت :
یکی از ایراد های روش ماتریس مجاورتی مشکل حذف و اضافه کردن گره هاست زیرا در این صورت اندازه ماتریس بایدتغییر کند. و
دلیل دیگر این است که اگر تعداد یال ها کم باشد(مثلا در گرافی n رأس تعداد یال ها n یا logn n)اباشد نگاه ماتریس خلوت به
وجود می آید و فضای زیادی اشغال میشود.
نکته 1: در یک گراف بدون جهت با n رأس و e یال نباز به آرایه ای به طول n و 2eگره لیست پیوندی است.
نکته2:در یک گراف جهت دار با n رأس و e یال نیاز به آرایه ای به طول n و e گره لیست پیوندی است.
نکته 3:اگر تعدا رأس ها گراف n باشد تعداد کل یال ها ) O)n+e تعیین می شود.
نکته 4:درجه هر رأس را در یک گراف بدون جهت را می توان با شمارش تعداد گره های آن در لیست مجاورتی تعیین نمود]]> رأس ها نشان دهنده اشیاء یا عناصر هستند و یال ها نشان دهنده روابط بین این عناصر هستند.
تعریف گراف :هر گراف را به صورت )G = )V,Eکه از مجموعه ناتهی از رأس ها )V)Vertex و مجموعه ای از یال های )E)Edge تشکیل شده است.
انواع گراف
جهت دار :
ترتیب گره ها در زوج مرتب اهمیت دارد.
2-غیرجهت دار :
گرافی است که درآن جای دو رأس در مجموعه یالها اهمیت نداشته باشد.

گراف پوچ :گرافی است که مجموعه یال های آن تهی باشد به عبارت دیگر یعنی فقط رأس ها در آن وجود دارند.
گره مجاور: گره X مجاور گره Y است اگر بین آنها یک یال وجود داشته باشد .
راس منفرد (منزوی) : رأسی که هیچ رأس مجاوری نداشته باشد.
طوقه (Loop ) : یالی که گره ابتدا و انتها آن یکی باشد.
گراف چندگانه (Multi Graph) : گرافی است که در آن داشتن یال های چندگانه و طوقه مجاز باشد.

گراف برچسب دار: گرافی است اطلاعاتی به یال های آن نسبت داده شده است.
گراف وزن دار : گرافی است که به هر یال آن یک مقدار عددی غیر منفی نسبت داده شده است.
گراف کامل (complete Graph) :گرافی است که بین هر دو رأس آنیک یال وجود دارد به عبارتی گرافی است که حداکثر تعداد یال
ها را دارد.

درجه گره : درجه گره برابر است با مجموع تعداد یال های متصل به یک گره .
درجه گراف : برابر است با بزرگترین درجه گره های گراف .
درجه ورودی : به تعداد یال های وارد شده به یک رأس در یک گراف جهت دار درجه ورودی آن رأس می گویند.
درجه خروجی : به تعداد یال های خارج شده از یک رأس در یک گراف جهت دار درجه خروجی آن رأس می گویند.
مسیر: مجموعه ای از یال های پشت سر هم که دو رأس را به هم وصل می کنند.
مسیر ساده : مسیری است که همه رأس های آن مجزا باشد به جز اولی و آخری .
طول مسیر : تعداد یال های موجود در مسیر است.
حلقه یا سیکل : مسیر ساده ای که گره اول و آخر آن یکی باشد.

گره چاه : گره ای که درجه خروجی صفر و درجه ورودی
مثبت داشته باشد را گره چاه می گوییم.
گره منبع : گره ای که درجه خروجی مثبت و درجه ورودی
صفر داشته باشد را گره منبع می گوییم.
گراف همبند و غیر همبند :
گراف همبند: یک گراف همبند گرافی است که درآن از هر
رأس می توان به تمام رأس های دیگراز طریق یال ها رسید .
به عبارت دیگر برای هر دو رأس دلخواه در گراف یک مسیر
از یال ها وجود دارد که این دو رأس را به هم وصل کند .
گراف ناهمبند : در گراف ناهمبند ممکن است بعضی رأس ها
به یکدیگر متصل نباشند به عبارت دیگر برای بعضی رأس ها
هیچ مسیری برای رسیدن به دیگر رأس ها وجود ندارد و
گراف به چند بخش مجزا تقسیم شود.

گراف جهت دار همبند قوی و ضعیف :
گراف همبند قوی جهت دار : در این نوع گراف بین هر جفت از رأس ها مسیر های جهت دار به طور کامل در هر دو جهت وجود دارند.یعنی اگر از یک رأس
شروع کنیم می توانیم به راس های دیگر برسیم.
گراف همبند ضعیف جهت دار: به گرافی گفته می شود که در آن جهت یال ها نادید گرفته شود به عبارت دیگر در این گراف هیچ گونه مسیری از یک رأس به
رأس های دیگر وجود نداشته باشد.
تفاوت درخت با گراف
1- درخت یک گراف بدون حلقه است که یک گره خاص بنام ریشه دارد و از ریشه ی درخت یک مسیر ساده به گره های دیگر وجود دارد. پس میتوان گفت که
درخت یک گراف متصل است.
2- پیمایش درخت از ریشه به گرههای دیگر صورت میپذیرد. پس میتوان گفتن ه درخت یک گراف جهت دار است .

ما به دو روش می توانیم گراف را نمایش دهیم :
1- ماتریس مجاورت 2- لیست مجاورت
1 – ماتریس مجاورت : ماتریس مجاورت یا همجواری یک گراف با n رأس آرایه ای n × n است که به صورت زیر تعریف می شود .
نکته1: ماتریس مجاورتی یک گراف بدون جهت حتما متقارن است و
می توان برای نگهداری آن از ماتریس بالا یا پایین مثلثی استفاده کرد.
نکته2:ماتریس مجاورت یا همجواری گراف جهت دار لزوما متقارن نیست.
نکته3: در ماتریس مجاورتی برای گراف جهت دار مجموع سطری درجه خروجی و مجموع ستونی درجه ورودی رأس نظیر یاسطر یا
ستون را نشان می دهد ولی برای گراف بدون جهت مجموع سطری یا ستونی درجه هر رأس نظیر است.
نکته 4:تعداد « 1» ها در ماتریس مجاورتی گراف بدون جهت دو برابر یال ها و در گراف جهت دار برابر با یال ها است .
نکته5: از نقاط قوت ماتریس مجاورتی می توان به سرعت دسترسی به مجاور بودن یا نبودن دو گره اشاره کرد که با زمان )O)1انجام
می شود.
نکته 6:با استفاده از ماتریس مجاورتی همه الگوریتم های لازم برای گراف با n رأس با زمان )O)n² انجام می شود

لیست مجاورت :
یکی از ایراد های روش ماتریس مجاورتی مشکل حذف و اضافه کردن گره هاست زیرا در این صورت اندازه ماتریس بایدتغییر کند. و
دلیل دیگر این است که اگر تعداد یال ها کم باشد(مثلا در گرافی n رأس تعداد یال ها n یا logn n)اباشد نگاه ماتریس خلوت به
وجود می آید و فضای زیادی اشغال میشود.
نکته 1: در یک گراف بدون جهت با n رأس و e یال نباز به آرایه ای به طول n و 2eگره لیست پیوندی است.
نکته2:در یک گراف جهت دار با n رأس و e یال نیاز به آرایه ای به طول n و e گره لیست پیوندی است.
نکته 3:اگر تعدا رأس ها گراف n باشد تعداد کل یال ها ) O)n+e تعیین می شود.
نکته 4:درجه هر رأس را در یک گراف بدون جهت را می توان با شمارش تعداد گره های آن در لیست مجاورتی تعیین نمود]]> http://forum.kishtech.ir/showthread.php?tid=111283 Mon, 23 Dec 2024 17:50:09 +0330 amirhossein shirazi]]> http://forum.kishtech.ir/showthread.php?tid=111283 2-چگونه می توان گراف های جهت دار و بدوت جهت را نمایش داد و در کدام موارد
هر یک از این روش ها مناسب تر است؟
3-ت فاوت های اصلی بین دو روش نمایش گراف ها، یعنی ماتریس مجاورت و لیست
مجاورت چیست؟
4-چگونه می توان گراف همبند و غیر همبند را از یکدیگرمتمایز کرد؟
5-چه زمانی استفاده از لیست مجاورت به جای ماتریس مجاورت مناسب تر است؟]]> 2-چگونه می توان گراف های جهت دار و بدوت جهت را نمایش داد و در کدام موارد
هر یک از این روش ها مناسب تر است؟
3-ت فاوت های اصلی بین دو روش نمایش گراف ها، یعنی ماتریس مجاورت و لیست
مجاورت چیست؟
4-چگونه می توان گراف همبند و غیر همبند را از یکدیگرمتمایز کرد؟
5-چه زمانی استفاده از لیست مجاورت به جای ماتریس مجاورت مناسب تر است؟]]> http://forum.kishtech.ir/showthread.php?tid=111280 Mon, 23 Dec 2024 17:31:56 +0330 amirhossein shirazi]]> http://forum.kishtech.ir/showthread.php?tid=111280
  نمونه سوال بخش اول گراف.pdf (اندازه: 70.89 KB / تعداد دفعات دریافت: 0) ]]>
  نمونه سوال بخش اول گراف.pdf (اندازه: 70.89 KB / تعداد دفعات دریافت: 0) ]]> http://forum.kishtech.ir/showthread.php?tid=111261 Mon, 23 Dec 2024 16:33:19 +0330 امیررضا82]]> http://forum.kishtech.ir/showthread.php?tid=111261

بتوانیم به راحتی به آنها دسترسی داشته باشیم. لیست پیوندی یکی از روشهای کارآمد برای نمایش گراف است، مخصوصاًاًوقتی میخواهیم یک گراف را نمایش دهیم، هدف این است که اطلاعات مربوط به راسها و یالها را به نحوی ذخیره کنیم که
.زمانی که تعداد یالها کمتر از تعداد تمام ترکیبهای ممکن بین راسها باشد (گراف خلوت یا کمتراکم)

در روش لیست پیوندی، به جای استفاده از ماتریس (که بیشتر حافظه رو مصرف میکنه)، برای هر راس یک لیست داریم که
راسهای متصل به اون رو ذخیره میکنه.این لیست نشان دهنده همسایگان گره است، که این لیست معمولا با استفاده از یک آرایه
.یا ساختار های دیگر پیاده سازی می شود

ساختار داده در این روش
ً هر راس یک لیست داره: مثلا راس (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) به کار میروند.
قابلیت پیادهسازی با ساختار دادههای مختلف: الگوریتم باید طوری طراحی شود که بتواند روی انواع ساختارهای ذخیرهسازی گراف (مثل
لیست مجاورت و ماتریس مجاورت) پیادهسازی شود.
یافتن مسیرها یا تعیین توالیها: الگوریتم باید بتواند اطلاعاتی درباره توالی بازدیدها یا مسیر بین راسها را ذخیره کند. این ویژگی به
خصوص برای حل مسائلی مثل پیدا کردن کوتاهترین مسیر، شناسایی مؤلفههای همبند و یافتن ترتیبهای خاص مفید است.
قابلیت استفاده در گرافهای وزندار و بدون وزن: الگوریتم باید طوری طراحی شود که هم در گرافهای وزندار و هم در گرافهای بدون وزن
قابل استفاده باشد. در گرافهای وزندار، ممکن است نیاز به تغییراتی در الگوریتم (مثل استفاده از الگوریتمهای دیگر برای کوتاهترین مسیر) باشد
پیمایش گراف یک فرآیند اساسیه که با الگوریتم سادهای انجام میشه. این الگوریتم به ترتیب همه نقاط متصل به هم رو پیدا و بازدید میکنه تا به
اطلاعات مختلفی در مورد ساختار و ویژگیهای گراف دسترسی داشته باشیم]]> http://forum.kishtech.ir/showthread.php?tid=111014 Sun, 22 Dec 2024 10:46:18 +0330 amirham]]> http://forum.kishtech.ir/showthread.php?tid=111014
  PS(1).pdf (اندازه: 68.95 KB / تعداد دفعات دریافت: 0) ]]>
  PS(1).pdf (اندازه: 68.95 KB / تعداد دفعات دریافت: 0) ]]> http://forum.kishtech.ir/showthread.php?tid=110655 Fri, 20 Dec 2024 15:57:36 +0330 Hossein ramezani]]> http://forum.kishtech.ir/showthread.php?tid=110655
الف)جستجوی دودویی
ب)مرتب‌سازی سریع
ج)مرتب‌سازی هرمی
د)درخت‌های AVL
۲.در یک هرم بیشینه (Max-Heap)، چه شرطی باید بین والد و فرزندان برقرار باشد؟

الف)مقدار والد کمتر از تمام فرزندان است.
ب)مقدار والد بزرگ‌تر یا مساوی تمام فرزندان است.
ج)مقدار والد برابر مجموع مقادیر فرزندان است.
د)هیچ قاعده خاصی وجود ندارد.
۳.ساختمان داده هرم معمولاً به چه صورت پیاده‌سازی می‌شود؟

الف)با استفاده از درخت دودویی پیوندی
ب)با استفاده از آرایه
ج)با استفاده از لیست پیوندی
د)با استفاده از جدول هش
۴.در یک هرم کمینه (Min-Heap)، چه شرطی باید برقرار باشد؟

الف)مقدار گره ریشه بزرگ‌تر از مقادیر تمام گره‌های فرزند است.
ب)مقدار گره ریشه کمتر از مقادیر تمام گره‌های فرزند است.
ج)گره ریشه همواره برابر مقدار میانی گره‌ها است.
ب)ترتیب مقادیر گره‌ها اهمیت ندارد.
۵.کدام یک از گزینه‌ها صحیح است؟

الف)هر درخت دودویی هرم است.
ب)هر آرایه می‌تواند به هرم تبدیل شود.
ج)هرم همیشه متعادل نیست.
د)هرم فقط در مرتب‌سازی داده‌ها استفاده می‌شود.]]>
الف)جستجوی دودویی
ب)مرتب‌سازی سریع
ج)مرتب‌سازی هرمی
د)درخت‌های AVL
۲.در یک هرم بیشینه (Max-Heap)، چه شرطی باید بین والد و فرزندان برقرار باشد؟

الف)مقدار والد کمتر از تمام فرزندان است.
ب)مقدار والد بزرگ‌تر یا مساوی تمام فرزندان است.
ج)مقدار والد برابر مجموع مقادیر فرزندان است.
د)هیچ قاعده خاصی وجود ندارد.
۳.ساختمان داده هرم معمولاً به چه صورت پیاده‌سازی می‌شود؟

الف)با استفاده از درخت دودویی پیوندی
ب)با استفاده از آرایه
ج)با استفاده از لیست پیوندی
د)با استفاده از جدول هش
۴.در یک هرم کمینه (Min-Heap)، چه شرطی باید برقرار باشد؟

الف)مقدار گره ریشه بزرگ‌تر از مقادیر تمام گره‌های فرزند است.
ب)مقدار گره ریشه کمتر از مقادیر تمام گره‌های فرزند است.
ج)گره ریشه همواره برابر مقدار میانی گره‌ها است.
ب)ترتیب مقادیر گره‌ها اهمیت ندارد.
۵.کدام یک از گزینه‌ها صحیح است؟

الف)هر درخت دودویی هرم است.
ب)هر آرایه می‌تواند به هرم تبدیل شود.
ج)هرم همیشه متعادل نیست.
د)هرم فقط در مرتب‌سازی داده‌ها استفاده می‌شود.]]> http://forum.kishtech.ir/showthread.php?tid=110652 Fri, 20 Dec 2024 15:44:50 +0330 Hossein ramezani]]> http://forum.kishtech.ir/showthread.php?tid=110652
  ساختمان داده هرم-محمدحسین رمضانی1.pdf (اندازه: 635.07 KB / تعداد دفعات دریافت: 0) ]]>
  ساختمان داده هرم-محمدحسین رمضانی1.pdf (اندازه: 635.07 KB / تعداد دفعات دریافت: 0) ]]> http://forum.kishtech.ir/showthread.php?tid=110525 Fri, 20 Dec 2024 00:33:23 +0330 محمد مهدی رمضانی]]> http://forum.kishtech.ir/showthread.php?tid=110525 الف) مرتب کردن دیسک‌ها بر اساس اندازه
ب) انتقال دیسک‌ها از یک میله به میله دیگر بدون شکستن قواعد
ج) حذف دیسک‌های اضافی
د) پیدا کردن کوتاه‌ترین مسیر

۲.در مسئله برج هانوی، چه قانونی برای حرکت دیسک‌ها وجود دارد؟
الف) دیسک کوچک‌تر نمی‌تواند روی دیسک بزرگ‌تر قرار گیرد.
ب) دیسک بزرگ‌تر نمی‌تواند روی دیسک کوچک‌تر قرار گیرد.
ج) دیسک‌ها باید به ترتیب اندازه جابه‌جا شوند.
د) همه دیسک‌ها باید به طور همزمان جابه‌جا شوند.

۳.حداقل تعداد حرکات مورد نیاز برای حل برج هانوی با 5 دیسک چند حرکت است؟
الف) 15
ب) 31
ج) 63
د) 127

۴.کدام روش معمولاً برای حل مسئله برج هانوی استفاده می‌شود؟
الف) جستجوی عمقی (DFS)
ب) روش تقسیم و حل (Divide and Conquer)
ج) برنامه‌ریزی پویا (Dynamic Programming)
د) الگوریتم حریصانه (Greedy Algorithm)

۵.اولین گام برای حل مسئله برج هانوی با سه دیسک چیست؟
الف) انتقال کوچک‌ترین دیسک به میله کمکی
ب) انتقال بزرگ‌ترین دیسک به میله مقصد
ج) انتقال دیسک وسط به میله کمکی
د) انتقال کوچک‌ترین دیسک به میله مقصد

۶.در مسئله برج هانوی، کدام یک از موارد زیر در هر حرکت رعایت می‌شود؟
الف) فقط یک دیسک در هر حرکت جابه‌جا شود.
ب) چندین دیسک به صورت همزمان قابل جابه‌جایی هستند.
ج) دیسک‌های کوچک‌تر همیشه در پایین‌ترین موقعیت قرار می‌گیرند.
د) می‌توان دیسک‌ها را از وسط بازی حذف کرد.

۷.برج هانوی برای چند دیسک با چه الگوریتمی می‌تواند بازگشتی حل شود؟
الف) انتقال دیسک به میله کمکی، انتقال دیسک آخر به مقصد، و سپس انتقال دوباره دیسک به میله مقصد
ب) انتقال همه دیسک‌ها به یکباره به میله مقصد
ج) انتقال بزرگ‌ترین دیسک به میله کمکی و ادامه کار
د) انتقال تصادفی دیسک‌ها تا حل مسئله]]> الف) مرتب کردن دیسک‌ها بر اساس اندازه
ب) انتقال دیسک‌ها از یک میله به میله دیگر بدون شکستن قواعد
ج) حذف دیسک‌های اضافی
د) پیدا کردن کوتاه‌ترین مسیر

۲.در مسئله برج هانوی، چه قانونی برای حرکت دیسک‌ها وجود دارد؟
الف) دیسک کوچک‌تر نمی‌تواند روی دیسک بزرگ‌تر قرار گیرد.
ب) دیسک بزرگ‌تر نمی‌تواند روی دیسک کوچک‌تر قرار گیرد.
ج) دیسک‌ها باید به ترتیب اندازه جابه‌جا شوند.
د) همه دیسک‌ها باید به طور همزمان جابه‌جا شوند.

۳.حداقل تعداد حرکات مورد نیاز برای حل برج هانوی با 5 دیسک چند حرکت است؟
الف) 15
ب) 31
ج) 63
د) 127

۴.کدام روش معمولاً برای حل مسئله برج هانوی استفاده می‌شود؟
الف) جستجوی عمقی (DFS)
ب) روش تقسیم و حل (Divide and Conquer)
ج) برنامه‌ریزی پویا (Dynamic Programming)
د) الگوریتم حریصانه (Greedy Algorithm)

۵.اولین گام برای حل مسئله برج هانوی با سه دیسک چیست؟
الف) انتقال کوچک‌ترین دیسک به میله کمکی
ب) انتقال بزرگ‌ترین دیسک به میله مقصد
ج) انتقال دیسک وسط به میله کمکی
د) انتقال کوچک‌ترین دیسک به میله مقصد

۶.در مسئله برج هانوی، کدام یک از موارد زیر در هر حرکت رعایت می‌شود؟
الف) فقط یک دیسک در هر حرکت جابه‌جا شود.
ب) چندین دیسک به صورت همزمان قابل جابه‌جایی هستند.
ج) دیسک‌های کوچک‌تر همیشه در پایین‌ترین موقعیت قرار می‌گیرند.
د) می‌توان دیسک‌ها را از وسط بازی حذف کرد.

۷.برج هانوی برای چند دیسک با چه الگوریتمی می‌تواند بازگشتی حل شود؟
الف) انتقال دیسک به میله کمکی، انتقال دیسک آخر به مقصد، و سپس انتقال دوباره دیسک به میله مقصد
ب) انتقال همه دیسک‌ها به یکباره به میله مقصد
ج) انتقال بزرگ‌ترین دیسک به میله کمکی و ادامه کار
د) انتقال تصادفی دیسک‌ها تا حل مسئله]]> http://forum.kishtech.ir/showthread.php?tid=110520 Fri, 20 Dec 2024 00:06:28 +0330 محمد مهدی رمضانی]]> http://forum.kishtech.ir/showthread.php?tid=110520
  برج هانوی و کاربرد آن- محمد مهدی رمضانی1.pdf (اندازه: 453.45 KB / تعداد دفعات دریافت: 1) ]]>
  برج هانوی و کاربرد آن- محمد مهدی رمضانی1.pdf (اندازه: 453.45 KB / تعداد دفعات دریافت: 1) ]]> http://forum.kishtech.ir/showthread.php?tid=110034 Tue, 17 Dec 2024 13:14:27 +0330 محمدجواد نوری نژاد]]> http://forum.kishtech.ir/showthread.php?tid=110034
1) به ریشه اصلی اشاره کند
2) به گره بعدی در پیمایش inorder اشاره کند
3) به گره بعدی در پیمایش preorder اشاره کند
4) به راست ترین گره درخت اشاره کند]]>
1) به ریشه اصلی اشاره کند
2) به گره بعدی در پیمایش inorder اشاره کند
3) به گره بعدی در پیمایش preorder اشاره کند
4) به راست ترین گره درخت اشاره کند]]> http://forum.kishtech.ir/showthread.php?tid=110033 Tue, 17 Dec 2024 13:11:08 +0330 محمدجواد نوری نژاد]]> http://forum.kishtech.ir/showthread.php?tid=110033
1) فرزند راست، فرزند چپ، گره والد
2) فرزند چپ، گره والد، فرزند راست
3)فرزند راست، گره والد، فرزند چپ
4، فرزند چپ، فرزند راست، گره والد]]>
1) فرزند راست، فرزند چپ، گره والد
2) فرزند چپ، گره والد، فرزند راست
3)فرزند راست، گره والد، فرزند چپ
4، فرزند چپ، فرزند راست، گره والد]]> http://forum.kishtech.ir/showthread.php?tid=110029 Tue, 17 Dec 2024 12:55:53 +0330 محمدجواد نوری نژاد]]> http://forum.kishtech.ir/showthread.php?tid=110029
1) پنج روش
2) سه روش
3) یک روش
4) دو روش]]>
1) پنج روش
2) سه روش
3) یک روش
4) دو روش]]> http://forum.kishtech.ir/showthread.php?tid=110026 Tue, 17 Dec 2024 12:41:41 +0330 محمدجواد نوری نژاد]]> http://forum.kishtech.ir/showthread.php?tid=110026
1) درخت دودویی نمیتواند تهی باشد ولی عمومی میتواند
2) در درخت عمومی فرزند راست و چپ مطرح است ولی در درخت دودویی تفاوتی ندارد؟
3) دخت دودویی میتواند تهی باشد ولی درخت عمومی نمیتواند
4) تفاوتی باهم ندارند]]>
1) درخت دودویی نمیتواند تهی باشد ولی عمومی میتواند
2) در درخت عمومی فرزند راست و چپ مطرح است ولی در درخت دودویی تفاوتی ندارد؟
3) دخت دودویی میتواند تهی باشد ولی درخت عمومی نمیتواند
4) تفاوتی باهم ندارند]]> http://forum.kishtech.ir/showthread.php?tid=110023 Tue, 17 Dec 2024 12:23:56 +0330 محمدجواد نوری نژاد]]> http://forum.kishtech.ir/showthread.php?tid=110023
1) تعداد ریشه ها دلخواه است
2) یک ریشه
3) حداقل 2ریشه
4) حداکثر 2 ریشه]]>
1) تعداد ریشه ها دلخواه است
2) یک ریشه
3) حداقل 2ریشه
4) حداکثر 2 ریشه]]>