آمار پرسش:
- پرسیده شده: 2020-12-25 10:22:56 -0600
- مشاهده شده: 285 بار
- بروز شده: 2022-03-06 11:03:22 -0600
پرسش‌های مشابه:
پیدا کردن راسی در درخت که دارای فاصله ی مینیمم است
یافتن کوچکترین پیچ و مهره با مقایسه آنها
آشپزباشی: مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
الگوریتمی برای کمینه کردن تعداد دفعات بازشدن کشوها
الگوریتم محاسبه لگاریتم-سوال مسابقه دانش آموزی صنعتی شریف
ادغام k آرایه‌ی مرتب شده با بهترین زمان اجرا
پیدا کردن مولفه های قویا همبند گراف جهت دار
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
الگوریتمی برای یافتن درخت فراگیر از یک گراف همبند ینویسید.
سلام دوستان،سوال اینه که الگوریتمی برای یافتن درخت فراگیر از یک گراف همبند بنوسید. ممنون میشم جوابشو بگین بهم
2 پاسخ
گراف G=(V,E) داده شده
قرار بده Vt و Et تهی باشد.(مجموعه رئوس و یالهای درخت فراگیر)
مجموعه رئوس ملاقات نشده U=V
یک راس دلخواه از G را انتخاب کن و در Vt قرار بده
قرا بده U=U-{v}
تا زمانیکه (U تهی نباشد) تکرار کن
یک یال مجاور e از رئوس Vt را انتخاب کن و در Et قرار بده
انتهای دیگر یال e را در Vt قرار بده
قرا بده U=U-{v}
T=(V,E) را برگردان
سلام ^__^
اول فرض کن یک درخت خالی داری.
از یک راس گراف شروع کن و اون رو به درخت اضافه کن الان درخت تو یک راس داره. حالا همه همسایه‌های اون راس رو انتخاب کن و با همون یال‌ها به درخت اضافه کن. حالا یک مجموعه از گره‌ها و یال‌ها داری.
همین کار رو برای راس‌های جدید تکرار کن. و اون قدر تکرار کن تا راسی در گراف باقی نمونه.
با این کاراولا چون گراف هم‌بنده، پس همه راس‌های گراف رو انتخاب خواهی کرد. دوما چون هر راس رو فقط یک بار انتخاب می‌کنی، چیزی که در نهایت حاصل میشه یک درخت خواهد بود.
