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

[amir_narmafzar]

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

[Sepidar]

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

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

[amir_narmafzar]

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

[Sepidar]

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

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

[Sepidar]

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

[Developer Programmer]

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


فرض می کنیم گرافمون هم بند باشه
یه نگاه به این لینک بکن... میخوام کروسکال رو بنویسم... اما نمیدونم چطور بفهمم که با اضافه کردن BD به مجموعه، سیکل تولید میشه
http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Kruskal_Algorithm_4.svg/200px-Kruskal_Algorithm_4.svg.png

[babila]

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

[k2ofk2s]

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 دور است.
در ضمن اگر پروژه ساختمان گسسته کامل خواستی بگو ... !!!!