الکوریتم گراف

[mehdi1362sh]

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

[mohandese_hiclass]

دوست عزیز من یه الگوریتمی الان به ذهنم رسید ولی باید بیشتر فکر کنم به شما هم میگم روش فکر کنید شاید به یک نتیجه ایی رسیدیم
ما بیام این کارو بکنیم که یالهارو به ترتیب حذف کنیم سپس الگوریتم های bfs,dfs رو صدا بزنیم اگه راسی بدون ملاقات مونده باشه پس گراف متصل نیست حالا می مونه فقط بررسی این که گراف دو اتصالی هست یا نه که اون هم صد در صد هست زیرا با حذف یک یال گراف حداکثر دو اتصالی می شود

[mehdi1362sh]

سلام
دوست عزیز از اینکه به این موضوع علاقه نشان دادید ممنونم.
ولی الگوریتمی که عنوان کردید هم زمانبر است وهم بهینه نیست .
من دنبال الگوریتمی هستم که از طریق پسته وپیمایشdfs بتواند یال های برشی راشناسایی کند

[mohandese_hiclass]

سلام
دوست عزیز از اینکه به این موضوع علاقه نشان دادید ممنونم.
ولی الگوریتمی که عنوان کردید هم زمانبر است وهم بهینه نیست .
من دنبال الگوریتمی هستم که از طریق پسته وپیمایشdfs بتواند یال های برشی راشناسایی کند

سلام دوست عزیز هزینش زیاد میشه ولی نه انقدر که نشه ازش استفاده کرد چون که اگه ما n تا یال داشته باشیم هزینه bfs dfs هم که حدودا n^2 هستش پس کلا میشه n^3 که فکر نکنم زیاده زیاد باشه باز اگه الگوریتم بهتری به نظرم رسید کوتاهی نمی کنم

[raha_hakhamanesh]

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

علاقه مند به سایر نظرات هستم