تبلیغات
بچه های مدرسه ی شهید مطهری - الگوریتم گابو
 
بچه های مدرسه ی شهید مطهری
این فقط یک وبلاگ مدرسه نیست !
درباره وبلاگ


سلام. این یک وبلاگ از مطالب متفاوت هستش ، که در اختیار شما می گذارم.شما می توانید انواع مطالب گوناگون و جالب را در این وبلاگ پیدا کنید.هر از چند گاهی هم خبر هایی در مورد مدرسه داده میشه.راستی نظر یادتون نره!

مدیر وبلاگ : 2fan
مطالب اخیر
نویسندگان
آمار وبلاگ
  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :

.

تماس با ما

الگوریتم چریَن- ملورن/ گابو در نظریه گراف، یک روش با پیچیدگی زمانی خطی برای یافتن مولفه‌های همبندی قوی در یک گراف جهتدار است . این الگوریتم در سال ۱۹۹۶ توسط جوزف چِریَن و
کورت ملورن ارائه شد و در سال 1999 توسط هارولد گابو بهبود یافت.
الگوریتم گابو همانند الگوریتم مولفه‌های همبند قوی تارجان، تنها یک جستجوی عمق اول در گراف داده شده انجام می‌دهد، و از یک پشته برای نگهداری گره‌هایی که
به مولفه‌ای اختصاص داده نشده‌اند استفاده می‌کند، و بعد از اختصاص دادن آخرین گره به مولفه همبندی، این گره‌ها را به یک مولفه‌ی جدید منتقل می‌کند.
الگوریتم تارجان از یک آرایه با اندیس گره‌ها شامل اعداد پیش‌ترتیب استفاده می‌کند، که به ترتیب دیده شدن در جستجوی عمق اول مقداردهی شده‌اند.
از آرایه‌ی پیش‌ترتیبی برای دانستن اینکه چه زمانی مولفه‌ی همبندی جدید ایجا شود استفاده می‌گردد. الگوریتم گابو به جای استفاده از آرایه، از پشته‌ی دیگری به این منظور استفاده می‌کند.

الگوریتم گابو

الگوریتم گابو با پشتیبانی دو پشته‌ی S و P یک جستجوی عمق اول بر روی گراف داده شده‌ی G انجام می‌دهد. پشته‌ی S تمامی گره‌هایی را تاکنون به یک مولفه‌ی همبندی قوی
اختصاص داده نشده‌اند، شامل می‌شود. گره‌ها در این پشته به ترتیبی که جستجوی عمق اول به آن می‌رسد قرار دارند. پشته‌ی P شامل گره‌هایی است که هنوز اختصاص آن‌ها به مولفه‌های همبندی
قوی متفاوت از هم، تعیین نشده است. همچنین در الگوریتم از یک شمارنده‌ی C که تعداد گره‌های مشاهده شده تاکنون است، برای محاسبه‌ی اعداد پیش‌ترتیب گره‌ها استفاده می‌شود.

هنگامی که جستجوی عمق اول به یک گره v می‌رسد، الگوریتم مراحل زیر را به ترتیب انجام می‌دهد:

  1. عدد پیش‌ترتیب v را برابر C قرار می‌دهد، و مقدار C را یکی افزایش می‌دهد.
  2. گره v را در پشته‌ی S و همینطور P قرار می‌دهد.
  3. برای هر یال از گره v به گره مجاور w :
    • اگر عدد پیش‌ترتیب w هنوز مقدار‎دهی نشده، به طور بازگشتی جستجو را روی w انجام می‌دهد؛
    • در غیر اینصورت، اگر w هنوز به یک مولفه‌ی همبندی قوی اختصاص داده نشده:
      • تا زمانی که عدد پیش‌ترتیب عنصر بالای پشته P، کمتر یا مساوی عدد پیش‌ترتیب w است، عنصر بالای P را خارج می‌کند.
  4. اگر v عنصر بالای P بود:
    • عناصر بالای S را تا زمانی که v خارج شود، خارج کرده و این عناصر را به یک مولفه‌ی همبندی اختصاص می‌دهد.
    • گره v را از P خارج می‌کند.

الگوریتم کلی شامل یک حلقه روی گره‌های گراف G است، که این جستجوی بازگشتی را برای گره‌هایی که هنوز عدد پیش‌ترتیب آن‌ها مقدار دهی نشده است، صدا می‌زند.





نوع مطلب : علمی، مقاله ها و تحقیق ها، 
برچسب ها :
لینک های مرتبط :

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