۱
subtitle
ارسال: #۱
فوری:الگوریتم تشخیص وجود دور
با سلام
من درسهای طراحی الگوریتم یادم رفته؛ کتابشم ندارم(کتاب SLR).
الگوریتم تشخیص وجود حلقه در گراف رو میخواستم.
میدونم که اگر شرط e|>|v|-1| برقرار باشه گراف حداقل یک دور داره. که برای undirected graphs درسته نه directed graphs.
حالا یک الگوریتم کلی میخواستم.
ممکنه راهنماییم کنید.
من درسهای طراحی الگوریتم یادم رفته؛ کتابشم ندارم(کتاب SLR).
الگوریتم تشخیص وجود حلقه در گراف رو میخواستم.
میدونم که اگر شرط e|>|v|-1| برقرار باشه گراف حداقل یک دور داره. که برای undirected graphs درسته نه directed graphs.
حالا یک الگوریتم کلی میخواستم.
ممکنه راهنماییم کنید.
۳
ارسال: #۲
RE: فوری:الگوریتم تشخیص وجود دور
الگوریتم CycleDetect
در این الگوریتم از روش جستجوی اول عمق استفاده شده است. ابتدا تمام گره ها برچسب white می گیرند. سپس هر گرهی که مشاهده می شود برچسب gray می گیرد و زمانی که تمام فرزندانش مشاهده شدند برچسب black می گیرد. اگر در حین جستجو به یک گره با برچسب gray رسیدیم، به این معنی است که در گراف دور وجود دارد. زمان اجرای الگوریتم تشخیص دور در گراف برابر با زمان اجرای الگوریتم جستجوی اول عمق است یعنی V+E است.
در این الگوریتم از روش جستجوی اول عمق استفاده شده است. ابتدا تمام گره ها برچسب white می گیرند. سپس هر گرهی که مشاهده می شود برچسب gray می گیرد و زمانی که تمام فرزندانش مشاهده شدند برچسب black می گیرد. اگر در حین جستجو به یک گره با برچسب gray رسیدیم، به این معنی است که در گراف دور وجود دارد. زمان اجرای الگوریتم تشخیص دور در گراف برابر با زمان اجرای الگوریتم جستجوی اول عمق است یعنی V+E است.
کد:
boolean cycleDetect(Graph g)
for each vertex v in g do
v.mark = WHITE
end for
for each vertex v in g do
if v.mark == WHITE then
if visit(g, v) then
return TRUE
end if
end if
end for
return FALSE;
boolean visit(Graph g, Vertex v)
v.mark = GREY
for each edge (v, u) in g do
if u.mark == GREY then
return TRUE
else if u.mark == WHITE then
if visit(g, u) then
return TRUE
end if
end if
end for
v.mark = BLACK
return FALSE
۱
ارسال: #۳
فوری:الگوریتم تشخیص وجود دور
تا اونجایی که من می دونم برای پیدا کردن دورها ، الگوریتم مستقیمی وجود نداره اما با استفاده از الگوریتم های موجود برای پیدا کردن "مولفه های متصل قوی" میشه به این سوال جواب داد.
به دوتا لینک زیر یه نگاهی بندازید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
به دوتا لینک زیر یه نگاهی بندازید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close