الگوریتم پیدا کردن دور در گراف؟

الگوریتم پیدا کردن دور در گراف؟

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

نمی دونم تونستم روش کارم رو برسونم یا نه؟

بله منظور شما متوجه شدم اما هدف من استفاده از الگوریتم بازگشتی؟؟؟؟؟؟؟؟؟؟؟
مثل nqueen

نقل قول:

---

بله منظور شما متوجه شدم اما هدف من استفاده از الگوریتم بازگشتی؟؟؟؟؟؟؟؟؟؟؟

---

این الگوریتمی که بنده عرض کردم رو به راحتی میشه به روش بزگشتی پیاده کرد:

function tagit(somenode):boolean

  Result=true

  if somenode is tagged then Result=false

  else

    tag(somenode)

    for each child of somenode do Result=Result and tagit(child)

  end if

  return Result

end function



function IsTree(somegraph):boolean

 return tagit(one of the nodes of somegraph)

end function

چه طور میشه مسیر های تکراری رو حذف کرد ؟
مثلا :
1 2 3 4 1 = 4 1 2 3 4

frd عزیز!
با عرض شرمندگی، لطفا دوباره اینجا پست کنید

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

نقل قول:

---

فرض می کنیم گرافمون هم بند باشه

---

یه نگاه به این لینک بکن... میخوام کروسکال رو بنویسم... اما نمیدونم چطور بفهمم که با اضافه کردن BD به مجموعه، سیکل تولید میشه
http://upload.wikimedia.org/wikipedi...ithm_4.svg.png

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

public void prodr( int v,ref int p, ref int[] pre, ref int[,] mtxg)

        {

           pre[p] = v+1;

            p++;

            for (int i = 0; i < mtxg.GetLength(0); i++)

                    if ( mtxg[v, i] >= 1)

                    {

                        mtxg[i, v] = 0;

                        mtxg[v, i] = 0;

                        prodr( i,ref p, ref pre, ref mtxg);

                    }

        }

هر یال که به گرافت با الگوریم کروسکال اضافه می کنی یک بار این تابع رو استفاده میکنی .
برای فراخوانی :
v شماره رآس اولین یال (کوچکترین یال ، توی شکل A )
P=0
[]pre آرایه ای به طول راس ها با مقادیر اولیه صفر
[،]mtxg ماتریس مجاورت گراف کنونی (یعنی گرافی که در الگوریتم ساخته شده)
بعد از انجام این متد pre را چک میکنی و اگر عدد (رآس ) تکراری در آن بود دور ایجاد شده .
این الگوریم در حقیقت پیمایش پیش ترتیب است ولی اگر گراف درخت نباشد دور ها را پیدا میکند
مثلا اگر pre اینطوری بود :1-2-3-4-7-3 ..... 3-4-7-3 دور است.
در ضمن اگر پروژه ساختمان گسسته کامل خواستی بگو ... !!!!