الگوریتم برای تشخیص دور و پیدا کردن دور با بیشترین وزن

[EngRbj]

سلام
یه الگوریتم می خوام که تو یه گراف جهت دار و وزن دار تشخیص دهد که آیا دور وجود دارد یا نه و اگر دور وجود دارد دور با بیشترین وزن را به من بدهد

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

[pesar irooni]

سوالت اشتباهه
اساسا دور با بیشترین وزن وجود نداره. چون اگه دوری وجود داشته باشه هر چقدر دور بزنیم وزن اون بیشتر میشه. بلکه بگیم دوری که در بردارنده دور دیگه ای نباشه و بیش از یک بار تکرار نشه.
بررسی وجود دور به وزن نیاز نداره و میشه به راحتی پیدا کرد: اگه تعداد یالها بزرگتر یا مساوی تعداد ندها باشه ما حتما دور داریم.
دور اویلری که از یک راس شروع بشه و تمام یالها رو میپیماید (که بیشترین وزن را میدهد) در زمان O(E) توسط جستجوی اول عمق پیدا میشه
اما پیدا کردن دور با بیشترین وزن رو میتونی با مساله دور همیلتونی (یا فروشنده دوره گرد) که یافتن دور با کمترین وزنه شبیه سازی کنی. فقط کافیه وزنها رو منفی کنی و مساله همیلتونی رو حل کنی.
اما اینو بدون که دور همیلتونی تو زمان چند جمله ای بدست نمیاد و زمان نمایی داره.

[tdkhakpur]

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