پروژه پایتون(8948)

---

شرح پروژه

موضوع :پروژه پایتون(1)

 با سلام خدمت مهندس عزيز

جسارتا سه سوال جداگانه در مورد مبحث ساختمان داه و بخصوص الگوریتم هاو گراف ها داشتم٬ممنون میشوم اگر مهندسان عزیز بتوانند کمکم کنند.

 سوال اول:

جسارتا درخواست داشتم شبهه کدی که برایتان در مورد الگوریتم جستجوی اول عمق گراف ها را فرستادم طوری تغییر دهید که:

۱) همه ی یال ها را همرا ه با نوع ان یال ها(یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی) در گراف جهت دار به عنوان خروجی نشان دهد.

۲)همچنین چه تغییراتی باید داده شود اگر گراف ما بدون جهت بود.

درخواستم از این سوال شبه کد تغییر داده شده است٬همراه با انالیز زمانی آن.

شبه کدها به زبان انگلیسی باشد ممنون میشوم.

: سوال دوم:

شبه کد سوال بالا را در پایتون جسارتا پیاده سازی بفرمایید به طوری که:

۱)ورودی برنامه باید یک فایل شامل ستی از  یال ها باشد که در گراف ورودی است.

به صورتی که اگر گراف شکل ۱ داده شود٬فایل ورودی ما  شامل لیستی مانند شکل ۲ است.

پیاده سازی کد جسارتا بایستی برای هر گرافی کار کند.

۲)نشان داده شود که اگر از گراف شکل ۱ استفاده کنیم٬خروجی این کد جیست؟

: سوال سوم:

یکی دیگر از راه های مرتب سازی توپولوژیکی(مرتب سازی موضعی) بر روی گراف جهت دار غیر مدور(Directed Acylic Graph) این است که پشت سر هم نود  با in-degree 0 را  پیدا کند٬آن را خروجی دهد و سپس آن نود را همراه با تمام یال های خروجی از ان نود پاک کند٬شبه کدی جسارتا طراحی بفرمایید که این ایده را نشان دهد و در زمان O(|E|+|V|)  اجرا شود.

این پروژه شامل 4 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

---

---