زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۵:۵۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

در مورد مبحث گراف ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

ارسال:
  

Pakzad پرسیده:

در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

سلام به همگی

در فصل ششم (نظریه گرافها) کتاب اقای قلی زاده در مورد الگوریتم دیکسترا (الگوریتم نزدیکترین همسایه)

میخواستم نحوه کار این الگوریتم را بدونم؟ (مرحله به مرحله)
لطفا توضیحات به صورت کد زبان برنامه نویسی نباشد.


در فصل هفتم (درختها) الگوریتم پریم مانند الگوریتم قبلی نحوه کار ان را بدونم؟ (مرحله به مرحله)
لطفا توضیحات به صورت کد زبان برنامه نویسی نباشد.

و در مورد پیمایش پیش ترتیبی و پس ترتیبی و میان ترتیبی نمی دونم از کجا بایستی شروع کنم مخصوصا پیمایش میان ترتیبی اگر در مورد هر کدام از این سه پیمایش توضیح جامع بدهید ممنون میشوم؟

برای مثال در صفحه ۳۲۱ یک مثال اورده شده کتاب ساختمان گسسته از اقای قلی زاده که من ضمیمه کرده‌ام (شکل شماره۲ نتیجه پیمایش میان ترتیبی از سمت چپ به راست بخوانید p j q f c k g a d r b h s m e i t n u

در این مثال از پایین ترین راس شروع کرده یعنی p

ولی در شکل شماره ۱ که ضمیمه کرده‌ام نتیجه پیمایش میان ترتیبی از سمت چپ به راست بخوانید: B H G A D C F

در این مثال از راس B شروع کرده چرا از راس H شروع نکرده است؟

با تشکر


فایل‌(های) پیوست شده


۰
ارسال:
  

انرژی مثبت پاسخ داده:

در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

در نمایش میان ترتیبی اول فرزند سمت جپ بعد پدر بعد فرزند سمت راست نوشته می شه در شکل ۱‌، اول به ریشه نگاه می کنه می بینه فرزند سمت چپ داره پس سراغ اون می ره(B) بعد به B نگاه می کنه ولی اون فرزند سمت چپ نداره پس طبق قانون فرزند چپ نداره پس نوبت به پدر میرسه بنابراین خود گره B نوشته می شه بعد سراغ فرزند راست B میره که G باشه دوباره برای G همین عملبات تکرار می شه یعنی بهش نگاه می کنه فرزند چپ داره پس اول اون نوشته می شه (H) بعد سراغ پدر میاد و نوشته می شه(G) بعد tرزند راست که نداره . حالا به ریشه درخت برمی گرده و به سمت راست میره و این عملیات دوباره تکرار می شه.

در مورد شکل ۲ از اون جایی که گره j فرزند چپ داره و اون هم p هست بنابراین اول اون نوشته می شه. همین روند رو ادامه بدید به جواب میرسید.کلا در پیمایش میان ترتیب، الین گرهی که نوشته می شه سمت چپ ترین گره در راستای ریشه درخته یعنی از ریشه برید سمت چپ تا جایی که دیگه سمت چپ نداشته باشه و اون گره نوشته می شه مثلا در مثال ۱ گره B این شرط رو داره و در شکل ۲ گره p

در نمایش پیش ترتیب همونطور که از اسمش مشخصه باید ریشه اول نوشته بشه بعد فرزند چپ بعد فرزند راست مثلا شکل ۱ رو در نظر بگیرید.اول باید ریشه نوشته بشه پس اول A رو می نویسیم بعد سراغ فرزند چپ میریم حال فرض کنید یه درخت جدید با ریشه B داریم دوباره اول ریشه نوشته می شه که همون B باشه بعد سمت چپ میریم ولی فرزند چپ نداره که بنویسیم بعد سمت راست میایم که به G میرسیم دوباره اول ریشه G بعد سمت چپ که H باشه بعد سمت راست که نداره پس تا این جا شد A B G H حالا همین عکلیات برای سمت راست درخت تکرار می شه.

پس در نمایش پیش ترتیب همیشه ریشه اولین گره ایست که نوشته می شه.


حالا واسه پس ترتیب هم همین عملیات رو تکرار کنید ولی ریشه باید اخر باشه اول فرزند چپ بعد فرزند راست بعد ریشه .هر مرحله که پایین رفتید برای زیر درخت دوباره این عملیات رو تکرار کنید.در نهایت اون چیزی که بدست میارید ریشه اخرین گره خواهد بود.

ارسال:
  

Pakzad پاسخ داده:

RE: در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده


خیلی ممنون از راهنماییتان
من یک شکل دیگه هم ضمیمه کرده‌ام لطفا پیمایش میان ترتیبی چگونه است؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

انرژی مثبت پاسخ داده:

در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

اگه طبق همون روند که گفتم پیش برید به heabdcgfjirmspknvtwqu می رسید اگه جاییش اشتباه بود یا نیاز به توضیح بیشتر بود بگید تا توضیح بدم

ارسال:
  

Pakzad پاسخ داده:

RE: در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

ممنون با تشکر از صبر و حوصله تان

جواب شما درست است
استدلال من این گونه است که (اگر اشتباه است اصلاح کنید جمله مرا اصلاح کنید)

یک درخت داریم ریشه اش r است از سمت چپ شروع میکنیم ما یک زیر درخت داریم که
راس ان j است دو فرزند با نامهای h,i دارد طبق قاعده از فرزند چپ شروع کرده یعنی h
را نوشته بعد بایستی به سراغ فرزند راست یعنی i برویم اما چون یک زیر درخت دیگری پایین
هست فرزند راست را نمینویسیم پس به سراغ زیر درخت دیگری با راس g رفته که شامل
فرزند چپ e فرزند راست f است باز مانند قبل نمی تونیم فرزند راست را بنویسیم چون
فرزند چپ پایین ان زیر درخت دیگری است با ریشه d و با فرزندان چپ a,b فرزند راست c
تو این مرحله دیگر چون زیر درخت دیگری نداریم طبق قاعده عمل میکنیم و بعد فرزندان راست
نوشته نشده را مینویسیم تا به ریشه اصلی یعنی r رسیده درخت بعدی را هم با این روش
پیمایش میکنیم.

اگر با یه راسی مانند h در این شکل روبرو شدیم که شامل یک زیر درخت باشد همیشه
بایستی یک مکث کرد یعنی ان زیر درخت بایستی تا اخر پیمایش شود بعد قاعده مورد نظر را رویش
پیاده کرد؟

در پیمایش پس ترتیبی همیشه از پایین‌تر سطح شروع کرده چون میگیم فرزند چپ و فرزند راست
بعد ریشه فکر کنم مثل این میمونه که بخواهی یک دیوار درست کنی که همیشه اجرها از پایین
چیده میشه میاید بالا درسته؟

در مورد الگوریتم دیکسترا مرحله اولش را میدونم مابقی مراحلش را خوب نمیدونم اگر
می دونید مرا راهنمایی کنید

با تشکر دوست عزیز
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

انرژی مثبت پاسخ داده:

در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

واسه میان ترتیبی اول فرزند چپ بعد ریشه بعد فرزند راست
حالا واسه این درخت:
ریشه درخت r هست .سراغ فرزند چپ میریم که باز هم یه زیر درخته با ریشه j. سراغ فرزند چپ که h باشه میریم.بز هم یه زیر درخت داریم.در این حالت باید مجددا ابترا سراغ فرزند چپ بریم بعد ریشه بعد فرزند راست. فرزند چپ نداره پس ریشه نوشته می شه یعنی h. حال سراغ فرزند راست میریم که اونم یه زیر درخته.د.باره تکرار این روند. یعنی ابتدا به فرزند چپش نگاه می کنیم که یه زیر درخته با ریشه e .فرزند چپ نداره که بنویسیم پس ریشه که e باشه نوشته می شه بعد میریم سراغ فرزند راست.باز زیر درخته با ریشه d .فرزند چپش باز یه زیر درخته با ریشه d .هرزند چپ اون a هست اون رو می نویسیم بعد ریشه که d باشه. بعد میایم بالا و ریشه زیر درخت یعنی d رو می نویسیم بعد سرراغ فرزند راست رفته و c رو نوشته .خوب حالا زیر درخت چپ g تموم شد پس ریشه یعنی g رو می نویسیم بعد فرزند راست یعنی f . خوب زیر درخت راست h هم تموم شد حالا زیر درخت چپ j هم تموم شد و ریشه یعنی خود J رو می نویسیم بعد فرزند راست یعنی i رو می نویسیم حالا زیر درخت چپ r تموم شد نوبت به ریشه میرسه یعنی r رو می نویسیم بعد سراغ زیر درخت راست میریم و ادامه عملیات ..... Smile

الگوریتم دایکسترا رو دقیقا یادم نیست اگه پیداش کردم براتون توضیحش رو می نویسم.

۰
ارسال:
  

Xilinx پاسخ داده:

در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

ممنون انرژی مثبت‌! من با روشی که یاد گرفته بودم فکر میکردم جواب یه چیزه دیگه میشه !
البته فکر میکنم روش های خیلی خیلی راحت تری واسه توضیح این ۳ پیمایش هست !

۰
ارسال:
  

انرژی مثبت پاسخ داده:

در مورد مبحث گراف‌ها و درخت کتاب ساختمان گسسته از اقای قلی زاده

اگر تمرین کنید نیازی به رفتن تمامی این مراحل نخواهید داشت در واقع در کمتر از یه دقیقه می تونید پیمایش رو دربیارید هر مسئله ای نیاز به تمرین و حل موارد مشابه داره



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۴۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۱,۳۰۳ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۹۶۶ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  دانلود جزوه ریاضیات گسسته amiraraz ۱ ۳,۲۲۰ ۰۴ خرداد ۱۴۰۱ ۰۳:۵۵ ب.ظ
آخرین ارسال: start2
  مبحث جستجوهای محلی Elham_tm ۷ ۳,۹۳۳ ۱۷ اسفند ۱۴۰۰ ۰۵:۴۳ ب.ظ
آخرین ارسال: KB2000
  معرفی منبع مناسب برای ارشد گسسته saharitst ۲۱ ۲۴,۴۹۵ ۲۲ دى ۱۴۰۰ ۰۶:۱۱ ب.ظ
آخرین ارسال: YasiAli
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  درخواست اپلود کتاب یا لینک دانلود کتاب+معرفی سایت دانلود کتاب ریحانه ۱۲۹ ۷۶,۸۹۶ ۱۱ آذر ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: Ariana2020
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۱۸۴ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close